Diese Sprachen unterstützen nicht gegenseitig rekursive Funktionen Optimierung "nativ", also ich denke, es muss Trampolin sein oder .. heh .. Umschreiben als Schleife) Vermisse ich etwas?
UPDATE: Es scheint, dass ich über FSharp gelogen habe, aber ich habe einfach kein Beispiel für gegenseitige Tail-Calls beim Googlen gesehen
Zuallererst unterstützt F # gegenseitig rekursive Funktionen nativ, da es von der tailcall Anweisung, die in .NET IL verfügbar ist, profitieren kann ( MSDN ). Dies ist jedoch ein wenig schwierig und funktioniert möglicherweise nicht auf einigen alternativen Implementierungen von .NET (z. B. Compact Frameworks), so dass Sie manchmal mit der Hand von Hand beschäftigen müssen.
Im Allgemeinen habe ich ein paar Möglichkeiten, damit umzugehen:
Trampoline - eine Exception auslösen, wenn die Rekursionstiefe zu hoch ist, und eine Schleife der obersten Ebene implementieren, die die Exception behandelt (die Exception würde Informationen zur Fortsetzung des Aufrufs enthalten). Anstelle der Ausnahme können Sie auch einfach einen Wert zurückgeben, der angibt, dass die Funktion erneut aufgerufen werden soll.
Mit Timer abwickeln - Wenn die Rekursionstiefe zu hoch ist, erstellen Sie einen Timer und geben ihm einen Callback, der nach sehr kurzer Zeit vom Timer aufgerufen wird (der Timer setzt die Rekursion fort) , aber der verwendete Stapel wird gelöscht).
Dasselbe könnte mit einem globalen Stack gemacht werden, der die Arbeit speichert, die erledigt werden muss. Anstatt einen Timer zu planen, würden Sie dem Stack Funktionen hinzufügen. Auf der obersten Ebene würde das Programm Funktionen aus dem Stapel auswählen und ausführen.
Um ein konkretes Beispiel für die erste Technik zu geben, könnten Sie in F # folgendes schreiben:
%Vor% Dies kann auch für gegenseitig rekursive Funktionen verwendet werden. Die imperative Schleife würde einfach die in f gespeicherte Funktion Call(f) aufrufen, bis sie Done mit dem Endergebnis erzeugt. Ich denke, das ist wahrscheinlich der sauberste Weg, dies zu implementieren.
Ich bin sicher, dass es andere ausgefeilte Techniken gibt, um mit diesem Problem umzugehen, aber das sind die beiden, die ich kenne (und die ich benutzt habe).
Nur um den Code griffbereit zu haben, wenn Sie Bing für F # gegenseitige Rekursion:
%Vor%Dies wird StackOverflow, wenn Sie ohne Tail-Aufrufe kompilieren (der Standard im "Debug" -Modus, die Stapel für einfacher Debuggen bewahrt), aber gut laufen, wenn mit Tail-Aufrufen kompiliert (der Standard im "Release" -Modus). Der Compiler führt Tail-Aufrufe standardmäßig aus (siehe --tailcalls ) und .NET-Implementierungen auf den meisten Plattformen ehren es.
Tags und Links scala optimization f# trampolines mutual-recursion