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.

Answer 1

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?