ndn - 8 months ago 74

Ruby 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 (

Answer

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.