ndn ndn - 8 months ago 74
Ruby Question

Ruby left vs right recursion

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

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

When I call these methods with a value over 9000 (


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.