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

Question

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.

I'd recommend running this through a debugger so you can see the call stack and relevant variables. — jhpratt, Mar 15 '19 at 04:01
@jhpratt Sorry, but what relevant variables? The only one, `num`, keeps getting dutifully decremented. And the call stack just says `"test.rb:6:in `rcall'",` once for each recursion, whether I add one to the call or not. — BobRodes, Mar 15 '19 at 04:15
It's easier if you start with the exit condition: when calling `rcall(10)` the first condition is met and the return value is `0`. When calling `rcall(11)`, the first condition is not met and the return value is `1 + rcall(10)` which evaluates to `1 + 0`. Likewise, `rcall(12)` is `1 + rcall(11)` = `1 + (1 + rcall(10))` = `1 + 1 + 0` and so on ... — Stefan, Mar 15 '19 at 09:09

max pleaner · Answer 1 · 2019-03-15T19:56:55.817

3

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?

edited Mar 15 '19 at 19:56

answered Mar 15 '19 at 04:07

max pleaner

26,189
9
66
118

Oh, well, heck. The return value is one plus the return value of the next call, which is 1, and so on. So, we're saying to return `1` each call and add it to all the other `1`'s that all the other calls return. And then the last one returns zero because we already have the count that we want -- typically. Ok, getting clearer. (Do I get this?) So, if we use your example, aren't we making four procedure calls really, which is why we put our exit condition at the beginning? – BobRodes Mar 15 '19 at 04:31
1

Please always mention the ability to enable TCO in MRI when answering questions about recursion `RubyVM::InstructionSequence.compile_option = { tailcall_optimization: true, trace_instruction: false }`, otherwise the above would quickly run out of stack. – Aleksei Matiushkin Mar 15 '19 at 05:52
@AlekseiMatiushkin I'm not that well-versed in this. Would the rcall function be able to use tailcall optimization without modification? – max pleaner Mar 15 '19 at 07:43
With the code in the question, where the subsequent call to itself is _the last instruction_, TCO is _possible_. To enable TCO (it’s off by default for some weird reason) in MRI, one should use the snippet I posted above. Basically, what TCO does, it cleans up the stack before passing the control. It’s possible if and only the calling instruction is the last one. That’s why **Tail** CO. – Aleksei Matiushkin Mar 15 '19 at 07:46
2

@AlekseiMatiushkin in the OP's code, the last "instruction" is the addition, not the method call. In order to get TCO working, the last expression has to be `rcall(...)`, not `1 + rcall(...)` (which apparently requires a different implementation). – Stefan Mar 15 '19 at 09:36
1

@Stefan indeed. `rcall` should take two arguments and sum the on itself. – Aleksei Matiushkin Mar 15 '19 at 09:41
Thank you for clarifying @Stefan, that was my suspicion. – max pleaner Mar 15 '19 at 16:59
@AlekseiMatiushkin That's the way I usually do it. So, you're saying that "should" be put together that way because it's a more efficient way to handle this particular need in a recursion, because it opens the way to TCO? – BobRodes Mar 15 '19 at 17:00
2

It’s not only _more efficient_, it allows technically infinite recursion, while the above would cause StackOverflow on ≈200th iteration. – Aleksei Matiushkin Mar 15 '19 at 17:06
@AlekseiMatiushkin Interesting. Thank you. :) – BobRodes Mar 15 '19 at 17:09
IIRC, you have to set the compile options in a different file or use some kind of `eval` – Stefan Mar 15 '19 at 17:38
As I now understand it, a tail call is more efficient because it can call the same instance of the method on the stack, rather than creating a new one as a "normal" recursive call does. – BobRodes Dec 30 '20 at 20:09

score 1 · Answer 2 · answered Mar 15 '19 at 05:32

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.

Yeah, I used it all the way back in the VB6 days once, to calculate a "sign and drive" payment for car leases in a state where the payment was taxable and the up-front costs weren't. It was a calculus problem where you had to keep recalculating and iterating down to the nearest penny, which is a good use case for recursion. The thing that seems to be the most obscure is the process of rolling it all together once the guard condition hits. I was asking whether specifically the technique of adding 1 to the call to get the count was specific to Ruby, not recursion in general. Obviously not. :) — BobRodes, Mar 15 '19 at 17:19

score 1 · Accepted Answer · answered Mar 15 '19 at 07:07

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

score 1 · Answer 4 · answered Mar 15 '19 at 15:58

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

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

4 Answers4