Why does this code cause a stack overflow?

Question

The following would cause stack overflow for large 'n', and I can understand why.

def factorial(n)
  (n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end

Why does the following cause overflow as well?

def factorial(n, k)
  (n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1))
end

Answer 1

Your second algorithm creates a n-long chain of lambda procedures, each containing a reference to the previous one. I don't know exactly what Ruby does, but in a properly tail-recursive language the stack would not overflow in your second algorithm, because k.call in the lambda is also in tail position. If, as Brian's experiment suggests, Ruby doesn't have proper tail calls, the n-long chain of nested calls to the lambda will overflow the stack when the head of the chain is invoked, even though Ruby is smart enough to convert the tail-recursive factorial call into a loop (= tail-call optimisation).

Answer 2

In most languages, function calls go onto the call stack, which is really just the stack. Calling a function recursively keeps adding to the call stack. Eventually you fill up the stack, and you get a stack overflow. That's always a danger when running a recursive function where your recursion level is going to be deep.

Answer 3

For the same reason the first one has a stack overflow... The callstack gets too large.