CODEWITHSUNDEEP
rubyrecursion
BobRodes
BobRodes

Reputation: 6165

Why does adding 1 to a recursive proc call return the count of calls made?

Suppose I have this code:

def rcall(num)
  return 0 if 10 == num
  1 + rcall(num - 1)
end

p rcall(90) # => 80

This code will always return 10 less than the value passed into num, i.e. the count of the recursive calls made.

I can't see how it works. I have a vague understanding that we return zero if the exit condition is met so as not to increment the counter again. But how, exactly, does adding one to the proc call increment the count of times called? I can't see where the incrementer is being accumulated.

Also, is this a technique specific to Ruby architecture, or is it more generally applicable? I haven't seen it mentioned in any answers to questions asking about how to count recursive calls; seems most of the time people pass a counter variable along to keep track of the count.

Upvotes: 3

Views: 428

Answers (4)

max pleaner
max pleaner

Reputation: 26758

Say you changed the base condition to return 0 if num.zero?, then calling it with argument 3 would look like this:

1 + rcall(2)
    # => 1 + rcall(1)
             # => 1 + rcall(0)
                      # => 0

which, if you replace the rcall invocations with their results (starting from the bottom), comes out to 1 + 1 + 1 + 0

In other words, you can understand it a little easier by going from the base case upward:

rcall(0)
# 0

rcall(1)
# the same as 1 + rcall(0), which is one

rcall(2)
# the same as 1 + rcall(1), which is two.

Hopefully you can see the pattern.

As was mentioned in the comments, you can optimize it like so:

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

def rcall(num, sum=0)
  return sum if 10 == num
  rcall(num - 1, sum + 1)
end

Though this may require some other setup, I'm not really sure.

See What Is Tail Call Optimization?

Upvotes: 3

periswon
periswon

Reputation: 626

That's not true in general. The important part is that rcall always returns 0 when it doesn't do a recursive call. Because of that you can add 1 to rcall when you call it recursively. You get for every recursive call a +1 and the +1 chain stops when the recursive calls stop.

This does also count the number of recursive calls but it will never stop counting:

def keep_counting
  2 + keep_counting + keep_counting
end

Upvotes: 1

iGian
iGian

Reputation: 11183

I just added some puts to your code, maybe it helps to follow the logic better than I can explain with my english.

So, this is the tweaked code:

def rcall(num)
  if 10 == num
    rec = 0
    puts "rec = #{rec} ---- End of recursion"
    return rec
  end
  rec = rcall(num - 1)
  res = 1 + rec
  puts "rec = #{rec} \t\t res = i + rec = #{res}"
  res
end

When you call on 15 for example, you get: rcall(15)

# rec = 0 ---- End of recursion
# rec = 0      res = i + rec = 1
# rec = 1      res = i + rec = 2
# rec = 2      res = i + rec = 3
# rec = 3      res = i + rec = 4
# rec = 4      res = i + rec = 5
# 5

If you call on a number less than 10, you never reach the end of the recursion, so no value is returned to build back the "call stack" and the error is raised: stack level too deep (SystemStackError)

Other languages supports recursion, for example Python. Here on famous Fibonacci (How to write the Fibonacci Sequence?).

I also want to share this Computerphile video about recursion on YouTube: https://youtu.be/Mv9NEXX1VHc

Upvotes: 1

red_menace
red_menace

Reputation: 3412

Recursion is one of those things that a lot of people know about, but not that many can describe it worth a damn (myself included). It is a general programming method that several languages support, not just Ruby.

Any given call stashes its current state when calling the method again, since it needs a value from that to continue. It is only when the deepest level returns a value (in this case 0) that the whole thing unwraps, since the previous calls now have values to work with (each adding 1). You are getting 10 less because you are using 10 as a "completion" value, essentially skipping anything smaller than the guard comparison (set the comparison to 0 or a negative number, for example).

In this case, the guard test avoids a "stack level too deep" error, since there isn't anything else to prevent a runaway recursion - you can see that by using an initial value less than the comparison, for example starting with 5 when the comparison is for 10.

Upvotes: 1

Related Questions