As continuações podem ser usadas como substituto para recursão?
-
20-09-2019 - |
Pergunta
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
Solução
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.
Outras dicas
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.
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