4

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
Sam
  • 6,240
  • 4
  • 42
  • 53
  • 1
    You don't need the parameter to inject, it defaults to the first element of the Enumerable it is called on. Also with a Ruby supporting Symbol#to_proc (1.8.7+, 1.8.6 + Facets) you can write factorial2 like this: (1..n).inject(&:*) – Michael Kohl Mar 17 '10 at 09:16

3 Answers3

5

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.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
1

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.

JRL
  • 76,767
  • 18
  • 98
  • 146
  • 2
    Every time I think I've "seen the Elephant," a snippet of Ruby comes along that makes me feel as green as the newest recruit. – Wayne Conrad Mar 17 '10 at 05:18
  • This solution doesn't work for me. Please post a complete solution. – Sam Mar 19 '10 at 02:38
  • I can't seem to get this formatted nicely, so here it is in uglytext. class Fact def fact(n, acc) if n==1 acc else fact(n-1, n*acc) end end tailcall_optimize :fact def factorial(n) fact(n,1) end end – Mark Wotton Aug 02 '10 at 04:18
0

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
tux21b
  • 90,183
  • 16
  • 117
  • 101
  • Ok, Ruby doesn't (always) do tail call optimization. So, on some ruby implementations this code might work and on others not... See here: http://stackoverflow.com/questions/824562/does-ruby-perform-tail-call-optimization – tux21b Mar 17 '10 at 00:45
  • This depends on the compiler/intepreter. Ruby does not guarantee tail-call optimization, as MRI Ruby itself is not tail-recursive. An implementation like MacRuby should be able to do it. – Chuck Mar 17 '10 at 00:47
  • Although my understanding of continuations is weak, can you please explain how tail recursive calls relate to continuations as I didn't think they were that related? – Kaleb Pederson Mar 17 '10 at 01:35
  • This implementation works for n < 4415 where as the one i provide above only works upto 2865 – Sam Mar 17 '10 at 22:43
  • @KalebPederson The tail call _is_ the continuation of a tail-recursive function since the caller effectively hands control over to the callee. – MauganRa Mar 31 '14 at 16:09