Peut-être continuations utilisés en remplacement de récursion?

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

Answer 1

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

Answer 2

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.

Answer 3

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