Continuaciones pueden ser utilizados como un sustituto de la recursividad?

Question

La siguiente función genera un 'nivel de pila demasiado profundo (SystemStackError)' para n = 5000

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

¿Hay una manera de evitar este error usando continuaciones / callcc?

Nota:

Sé que esto puede ser implementado sin recursividad. por ejemplo.

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

Answer 1

Claro. Continuaciones pueden hacer nada! Sin embargo, usted va a terminar reinventar una de dos cosas: un bucle o una llamada de función. En mi máquina, lo que hace la optimización de llamada por defecto, la recursión de cola con llamada / cc qué no get optimizado. El programa se atasca de forma rápida, ya que cada callcc aparentemente capta toda la pila de llamadas. Ese código está roto, aquí es un bucle de llamada / cc:

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

Nota:. previamente me había olvidado esa llamada / cc no se trata sólo de iniciar una cadena de continuación pasa y se confundió sobre la necesidad de la repetición, por lo tanto, los comentarios a continuación

Answer 2

Puede activar la optimización de llamada con tailcall_optimize :factorial, tomada de aquí .

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

este post interesante de determinar si se ha activado la recursión de cola.

Answer 3

El problema es que la función devuelve factorial(n -1) * n que es una expresión y no hay ninguna llamada recursiva sola. Si logran tener sólo la llamada función en la instrucción de retorno, entonces la función se llama cola recursiva , y un buen compilador / intérprete (no estoy seguro de si Ruby es capaz de ello) puede hacer algunas optimizaciones para evitar el uso de la pila.

Tal función recursiva de cola podría tener este aspecto, pero tenga en cuenta que no soy un programador Ruby, así que no estoy acostumbrado a la sintaxis ni a las características del intérprete. Sin embargo, es posible que pueda probarlo por su cuenta:

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