Can continuations be used as a replacement for recursion?

Question

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

Answer 1

The problem is, that the function returns factorial(n -1) * n which is a expression and no single recursive call. If you manage to have only the function call in the return statement, then the function is called tail recursive, and a good compiler / interpreter (i am not sure if Ruby is capable of it) can do some optimizations to avoid the usage of the stack.

Such a tail-recursive function might look like this, but please note that I'm not a Ruby programmer, so I am neither used to the syntax nor to the features of the interpreter. But you might be able to try it on your own:

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

Answer 2

You can enable tail-call optimization with 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 about determining if tail recursion is enabled.

Answer 3

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.