CODEWITHSUNDEEP
rubyrecursion
g06lin
g06lin

Reputation: 6085

Why does this code cause a stack overflow?

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

Upvotes: 7

Views: 674

Answers (4)

Anton Tykhyy
Anton Tykhyy

Reputation: 20076

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).

Upvotes: 9

Matt Grande
Matt Grande

Reputation: 12157

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

Upvotes: 2

Brad Barker
Brad Barker

Reputation: 2083

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.

Upvotes: 3

Humphrey Bogart
Humphrey Bogart

Reputation: 7613

As in the first function, the recursive calls can end up being too many for the system to handle.

Upvotes: 0

Related Questions