Peut-être continuations utilisés en remplacement de récursion?
-
20-09-2019 - |
Question
La fonction suivante génère un 'niveau de pile trop profonde (SystemStackError)' pour n = 5000
def factorial(n)
n == 0 ? 1 : factorial(n -1) * n
end
Y at-il un moyen d'éviter cette erreur en utilisant continuations / callcc?
Remarque:
Je sais que cela peut être mis en œuvre sans récursivité. par exemple.
def factorial2(n)
(1..n).inject(1) {|result, n| result * n }
end
La solution
Bien sûr. Continuations peut faire quoi que ce soit! Cependant, vous finirez par réinventant une des deux choses: une boucle ou un appel de fonction. Sur ma machine, qui fait appel optimisation de la queue par défaut, récursion arrière avec appel / cc ne pas get optimisé. Le programme tourbières rapidement vers le bas comme chaque callcc
capture apparemment toute la pile d'appel. Ce code étant cassé, voici une boucle d'appel / 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
Remarque:. auparavant, je l'avais oublié cet appel / cc n'est pas seulement lancer une chaîne passant de continuation et obtenu confus au sujet de la nécessité de récursivité, d'où les commentaires ci-dessous
Autres conseils
Vous pouvez activer l'optimisation d'appel de queue avec tailcall_optimize :factorial
, tiré de .
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
Voir cet article intéressant sur la détermination si récursion de la queue est activée.
Le problème est que la fonction retourne factorial(n -1) * n
qui est une expression et pas un seul appel récursif. Si vous parvenez à avoir que l'appel de fonction dans l'instruction de retour, alors la fonction est appelée tail récursive , et un bon compilateur / interpréteur (je ne sais pas si Ruby en est capable) peut faire un peu optimisations pour éviter l'utilisation de la pile.
Une telle fonction récursive pourrait ressembler à ceci, mais s'il vous plaît noter que je ne suis pas un programmeur Ruby, donc je ne suis ni habitué à la syntaxe ni aux caractéristiques de l'interprète. Mais vous pourriez être en mesure de l'essayer sur votre propre:
def factorial(n, result=1)
n == 0 ? result : factorial(n-1, result * n)
end