Can continuations be used as a replacement for recursion?
continuations, recursion, ruby
Solution
Sure. Continuations can do anything! However, you'll end up reinventing one of two things: a loop or a function call. On my machine, which does tail-call optimization by default, tail recursion with call/cc does not get optimized. The program quickly bogs down as each `callcc` apparently captures the entire call stack. That code being broken, here is a call/cc loop:
def fact( n )
(n, f, k) = callcc { |k| [ n, 1, k ] }
if ( n == 0 ) then return f
else k.call n-1, n*f, k
end
end
Note: previously I'd forgotten that call/cc isn't just about initiating a continuation-passing chain and got confused about the need for recursion, hence the comments below.
Problem
The following function generates a 'stack level too deep (SystemStackError)' for n = 5,000 ``` def factorial(n) n == 0 ? 1 : factorial(n -1) * n end ``` Is there a way to avoid this error using continuations/callcc? Note: I know this can be implemented without recursion. e.g. ``` def factorial2(n) (1..n).inject(1) {|result, n| result * n } end ```