As continuações podem ser usadas como substituto para recursão?

Question

A função a seguir gera um 'nível de pilha muito profundo (SystemStackError)' para n = 5.000

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

Existe uma maneira de evitar esse erro usando continuações/calcc?

Observação:

Eu sei que isso pode ser implementado sem recursão. por exemplo

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

Answer 1

Claro. As continuações podem fazer qualquer coisa! No entanto, você acabará reinventando uma das duas coisas: um loop ou uma chamada de função. Na minha máquina, que faz a otimização de chamada de cauda por padrão, a recursão de cauda com chamada/cc faz não Seja otimizado. O programa rapidamente se apaga como cada um callcc Aparentemente, captura a pilha de chamadas inteira. Esse código está sendo quebrado, aqui está um loop de chamada/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

Observação: Anteriormente, eu tinha esquecido que a chamada/CC não é apenas iniciar uma cadeia que passasse de continuação e fiquei confusa sobre a necessidade de recursão, daí os comentários abaixo.

Answer 2

Você pode ativar a otimização de chamada de cauda com tailcall_optimize :factorial, Tirado de aqui.

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

Ver Este post interessante sobre determinar se a recursão da cauda está ativada.

Answer 3

O problema é que a função retorna factorial(n -1) * n que é uma expressão e nenhuma chamada recursiva. Se você conseguir ter apenas a chamada de função na declaração de retorno, a função é chamada cauda recursiva, e um bom compilador / intérprete (não tenho certeza se o Ruby é capaz disso) pode fazer algumas otimizações para evitar o uso da pilha.

Uma função tão recursiva de cauda pode ficar assim, mas observe que não sou um programador de rubi, por isso não estou acostumado à sintaxe nem aos recursos do intérprete. Mas você pode experimentá -lo por conta própria:

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