Can continuations be used as replacements for recursion?

Question

The following function generates a stack level too high (SystemStackError) for n = 5000

def factorial(n) n == 0 ? 1 : factorial(n -1) * n end 

Is there a way to avoid this error using continue / callcc?

Note:

I know that this can be implemented without recursion. eg.

 def factorial2(n) (1..n).inject(1) {|result, n| result * n } end 

Answer 1

Of course. A sequel can do anything! However, you end up inventing one of two things: a loop or a function call. On my machine, which by default performs tail call optimization, tail recursion with the / cc call is not optimized. The program quickly fades, as each callcc seems to grab the entire call stack. This code is broken, here is the / cc call 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: earlier I forgot that call / cc does not just initiate the chain to continue the transfer and got confused about the need for recursion, so the comments are below.

Answer 2

You can enable tail call optimization using tailcall_optimize :factorial , taken from here .

 class Class def tailcall_optimize( *methods ) methods.each do |meth| org = instance_method( meth ) define_method( meth ) do |*args| if Thread.current[ meth ] throw( :recurse, args ) else Thread.current[ meth ] = org.bind( self ) result = catch( :done ) do loop do args = catch( :recurse ) do throw( :done, Thread.current[ meth ].call( *args ) ) end end end Thread.current[ meth ] = nil result end end end end end 

See this interesting post on determining whether tail recursion is enabled.

Answer 3

The problem is that the function returns factorial(n -1) * n , which is an expression and does not have a single recursive call. If you can only call the function in the return statement, the function is called tail recursive , and a good compiler / interpreter (I'm not sure Ruby is capable of this) can do some optimizations to avoid using the stack.

Such a tail-recursive function might look like this, but remember that I'm not a Ruby programmer, so I'm not used to the syntax and functions of the interpreter. But you can try it yourself:

 def factorial(n, result=1) n == 0 ? result : factorial(n-1, result * n) end