mnoronha mnoronha - 2 months ago 7
Ruby Question

Return behavior for recursion in Ruby

I was working on a simple recursive method to implement Euclid's algorithm in Ruby, and find myself stuck figuring out how to return the desired value once the base case is reached. Here's what I have to far:

def euclid_alg(larger,smaller)
if larger % smaller == 0 && smaller != 1
return smaller
else
puts 'calling self'
euclid_alg(smaller, (larger % smaller))
puts 'executed section after call'
end
puts "made it here #{smaller} #{larger}"
nil
end
puts euclid_alg(100,15)


And the output:

calling self
calling self
executed section after call
made it here 10 15
executed section after call
made it here 15 100


Note there is no output from "puts euclid_alg(100,15)" which I was expecting to return the greatest common divisor of 100 and 15, 5.

In order to troubleshoot, I replaced the
return smaller
on line 3 with
puts smaller
. The new output was:

calling self
calling self
5
made it here 5 10
executed section after call
made it here 10 15
executed section after call
made it here 15 100


The addition of the "made it here 5 10" to the console output makes it clear that the return statement is breaking out of the function call, but not "parent calls."

How can I do recursion better?

Answer

Your code is just fine. You are simply missing a return. Note:

def euclid_alg(larger,smaller)
  if larger % smaller == 0 && smaller != 1
    return smaller
  else
    puts 'calling self'
    return euclid_alg(smaller, (larger % smaller)) # <<<<<  Return here
    puts 'executed section after call'
  end
  puts "made it here #{smaller} #{larger}"
  nil
end
puts euclid_alg(100,15)
Comments