Return behavior for recursion in Ruby

Question

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?

Readers: from the Wiki, the Euclidean algorithm "is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder." — Cary Swoveland
– Cary Swoveland, Commented Sep 10, 2016 at 1:43

David Hoelzer · Accepted Answer · 2016-09-10 01:48:45Z

3

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)

answered Sep 10, 2016 at 1:48

David Hoelzer

16.4k4 gold badges54 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Return behavior for recursion in Ruby

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related