Ruby left vs right recursion

Question

For some reason Ruby seems to perform better when facing left recursion. For example:

def left_recursive_factorial(number)
  return 1 if number.zero?
  left_recursive_factorial(number.pred) * number
end

def right_recursive_factorial(number)
  return 1 if number.zero?
  number * right_recursive_factorial(number.pred)
end

When I call these methods with a value over 9000 (😉) I get different results:

left_recursive_factorial(9001)
  # => factorial of 9001

right_recursive_factorial(9001)
  # => SystemStackError: stack level too deep
  #    from (pry):6:in `right_recursive_factorial'

I couldn't find any explanation for this behavior.

The only thing that seemed somewhat related was about LL() parsers having problems with left recursion and I guess you can flip it around, but I haven't dug much into it.

Could someone explain in a little more detail what causes left and right recursions to perform differently (generally and in Ruby specifically) and if you have the possibility to choose one or the other why would you pick it (and why was left chosen in Ruby)?

Answer 1

OK, I am not a YARV hacker of any sort, but here's the difference as I understand it. When you call a method, the sender pushes the method's arguments onto the stack, then the called method pops its arguments off and pushes its return value on. With the recursive call first, the number argument hasn't been pushed onto the stack yet, so the stack of each call takes slightly less space. This is why you can get a few more iterations out of that version, but not drastically more — you're looking at a few percent reduction in stack usage.