Rekursive Funktionen, Stapelüberläufe und Y-Kombinatoren

Question

Ich habe eine rekursive Funktion (in C #), die ich ungefähr 800 Millionen Mal aufrufen muss.Dies würde offensichtlich normalerweise zu einem Stapelüberlauf nach etwa dem 900. Aufruf führen.Ich habe dies in mehrere Schleifen geworfen, aber das rekursive Muster ist viel einfacher und sauberer zu pflegen.

Ich möchte die rekursive Funktion mithilfe eines y-Kombinators implementieren, wie ich gelesen und gesehen habe, um das Stapelüberlaufproblem zu lösen und die mehreren verschachtelten Schleifen zu beheben.

Hat jemand Erfahrung mit dem y-Kombinator?Werde ich immer noch in einem Stapelüberlauf stecken bleiben?

Nehmen Sie das einfache Beispiel einer Fakultät.Eine Fakultät für die meisten Zahlen größer als 5.000 führt zu einem Stapelüberlauf.Wenn ich in diesem Szenario einen y-Kombinator richtig verwenden würde, würde er den Stapelüberlauf beheben?

Die Implementierung scheint nicht trivial zu sein, daher möchte ich sie bestätigen, bevor ich den Entwicklungsaufwand / die Ressourcen für die Implementierung und das Erlernen des y-Kombinators aufgewendet habe.

Answer 1

Nein, die Verwendung des Y-Kombinators hilft Ihrer Situation nicht.Wenn Sie 800 Millionen Mal etwas tun müssen, können Sie entweder (a) rekursiv oder (b) schleifen (oder ich nehme an, (c) 800 Millionen Aufrufe an Ihre Funktion schreiben).Da der Y-Kombinator keine Schleife ausführt, muss er daher erneut ausgeführt werden.

Sie suchen nach einer Schleife, es sei denn, Sie verwenden eine Laufzeitumgebung, die eine ordnungsgemäße Schwanzrekursion bietet (z. B. Schema).

Trotzdem ist die Implementierung des Y-Kombinators von Grund auf in der Sprache Ihrer Wahl eine hervorragende Übung.

Answer 2

Y-Kombinatoren sind nützlich, aber ich denke, Sie möchten wirklich eine Optimierung der Schwanzrekursion , die die Verwendung des Stapels für rekursive Funktionen des Schwanzes eliminiert.Eine Schwanzrekursion ist nur möglich, wenn das Ergebnis jedes rekursiven Aufrufs sofort vom Anrufer zurückgegeben wird und niemals eine zusätzliche Berechnung nach dem Anruf.Leider unterstützt C # die Optimierung der Schwanzrekursion nicht, Sie können sie jedoch mit einem Trampolin emulieren, was eine einfache Konvertierung von der Methode der Schwanzrekursion in eine Methode mit Trampolinumhüllung ermöglicht.

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}

Answer 3

Sie können Trampolin verwenden, wie es in Reactive Extension verwendet wird. Ich habe versucht, es in meinem Blog zu erklären. http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Eine Lösung besteht darin, Ihre Funktion (en) in eine Schleife und eine explizite Kontext -Datenstruktur zu konvertieren. Der Kontext repräsentiert das, was die Leute allgemein als Aufrufstapel betrachten. Möglicherweise finden Sie meine Antwort auf eine andere Frage über die Konvertierung in Schwanzrekursion nützlich. Die relevanten Schritte sind 1 bis 5; 6 und 7 sind spezifisch für diese bestimmte Funktion, während Ihre komplizierter klingt.

Die "einfache" Alternative besteht jedoch darin, jeder Ihrer Funktionen einen Tiefenzähler hinzuzufügen. Wenn es ein Limit erreicht (bestimmt durch Experimente), erzeugen Sie einen neuen Thread, um die Rekursion mit einem neuen Stapel fortzusetzen. Der alte Thread blockiert das Warten auf das Senden eines Ergebnisses durch den neuen Thread (oder wenn Sie ausgefallen sein möchten, ein Ergebnis oder eine Ausnahme, die erneut ausgelöst werden soll). Der Tiefenzähler geht für den neuen Thread auf 0 zurück. Wenn das Limit erreicht ist, erstellen Sie einen dritten Thread und so weiter. Wenn Sie Threads zwischenspeichern, um zu vermeiden, dass die Kosten für die Thread-Erstellung häufiger als nötig bezahlt werden, erhalten Sie hoffentlich eine akzeptable Leistung, ohne Ihr Programm drastisch umstrukturieren zu müssen.