Kann Fortsetzungen als Ersatz für Rekursion verwendet werden?

Question

Die folgende Funktion erzeugt eine 'Stapelebene zu tief (SystemStackError)' für n = 5,000

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

Gibt es eine Möglichkeit, diesen Fehler mit Fortsetzungen / callcc zu vermeiden?

Hinweis:

Ich weiß, das ohne Rekursion implementiert werden kann. z.

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

Answer 1

Klar. Fortsetzungen kann alles tun! Allerdings werden Sie auf neu zu erfinden eine von zwei Dingen am Ende: eine Schleife oder einen Funktionsaufruf. Auf meinem Rechner, die standardmäßig Endrekursion mit Call-Tail-Call-Optimierung tut / cc tut nicht optimiert erhalten. Das Programm schnell versinkt wie jeder callcc fängt scheinbar den gesamten Call-Stack. Dieser Code ist gebrochen, hier ist ein Aufruf / cc-Schleife:

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

. Hinweis: vorher hatte ich vergessen, dass Anruf / cc ist nicht nur über eine Fortsetzung Umgehung Kette initiiert und wurde über die Notwendigkeit einer Rekursion verwirrt, daher werden die Kommentare unten

Answer 2

Sie können Tail-Call-Optimierung mit tailcall_optimize :factorial, genommen von ermöglichen hier .

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

Siehe dieser interessante Beitrag um zu bestimmen, ob Endrekursion aktiviert ist.

Answer 3

Das Problem ist, dass die Funktion zurückkehrt factorial(n -1) * n, die ein Ausdruck und kein einzelner rekursiven Aufruf ist. Wenn es Ihnen gelingt nur den Funktionsaufruf in der return-Anweisung zu haben, dann wird die Funktion namens Schwanz rekursive , und ein guter Compiler / Interpreter (ich bin nicht sicher, ob Ruby-fähig ist, es ist) tun können, einige Optimierungen die Verwendung des Stapels zu vermeiden.

Eine solche tail-rekursive Funktion könnte wie folgt aussehen, aber beachten Sie bitte, dass ich nicht ein Ruby-Programmierer, so dass ich weder auf die Syntax verwendet werde noch auf die Funktionen des Interpreters. Aber Sie könnten in der Lage sein, es zu versuchen, auf eigene Faust:

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