Ich habe den folgenden Code, der mit dem folgenden Fehler fehlschlägt:

RuntimeError: Maximale Rekursionstiefe überschritten

Ich habe versucht, dies neu zu schreiben, um die Optimierung der Schwanzrekursion (TCO) zu ermöglichen. Ich glaube, dass dieser Code erfolgreich gewesen sein sollte, wenn eine TCO stattgefunden hätte.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Sollte ich zu dem Schluss kommen, dass Python keine TCO durchführt, oder muss ich es nur anders definieren?

Nein, und das wird es auch nie, da Guido van Rossum es vorzieht, richtige Rückverfolgungen zu haben:

Eliminierung der Schwanzrekursion (2009-04-22)

Letzte Worte zu Tail Calls (27.04.2009)

Sie können die Rekursion mit einer Transformation wie folgt manuell entfernen:

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500

Ich habe ein Modul veröffentlicht, das die Tail-Call-Optimierung durchführt (sowohl die Tail-Rekursion als auch den Continuation-Passing-Stil): https://github.com/baruchel/tco

Optimierung der Schwanzrekursion in Python

Es wurde oft behauptet, dass die Schwanzrekursion nicht zur pythonischen Codierungsmethode passt und dass man sich nicht darum kümmern sollte, wie man sie in eine Schleife einbettet. Ich möchte mit diesem Standpunkt nicht streiten. Manchmal mag ich es jedoch aus verschiedenen Gründen, neue Ideen als schwanzrekursive Funktionen anstatt mit Schleifen zu versuchen oder zu implementieren (ich konzentriere mich eher auf die Idee als auf den Prozess, habe zwanzig kurze Funktionen gleichzeitig auf meinem Bildschirm und nicht nur drei "Pythonic"). Funktionen, die in einer interaktiven Sitzung arbeiten, anstatt meinen Code zu bearbeiten usw.).

Die Optimierung der Schwanzrekursion in Python ist in der Tat recht einfach. Es soll zwar unmöglich oder sehr knifflig sein, aber ich denke, es kann mit eleganten, kurzen und allgemeinen Lösungen erreicht werden. Ich denke sogar, dass die meisten dieser Lösungen Python-Funktionen nicht anders verwenden, als sie sollten. Saubere Lambda-Ausdrücke, die mit Standardschleifen zusammenarbeiten, führen zu schnellen, effizienten und vollständig verwendbaren Tools für die Implementierung der Optimierung der Schwanzrekursion.

Aus persönlichen Gründen habe ich ein kleines Modul geschrieben, das eine solche Optimierung auf zwei verschiedene Arten implementiert. Ich möchte hier über meine beiden Hauptfunktionen diskutieren.

Der saubere Weg: Modifizieren des Y-Kombinators

Der Y-Kombinator ist bekannt; Es erlaubt die rekursive Verwendung von Lambda-Funktionen, erlaubt es jedoch nicht, rekursive Aufrufe in eine Schleife einzubetten. Lambda-Kalkül allein kann so etwas nicht. Eine geringfügige Änderung des Y-Kombinators kann jedoch den rekursiven Aufruf schützen, der tatsächlich ausgewertet werden soll. Die Auswertung kann sich somit verzögern.

Hier ist der berühmte Ausdruck für den Y-Kombinator:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

Mit einer sehr kleinen Änderung konnte ich bekommen:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

Anstatt sich selbst aufzurufen, gibt die Funktion f jetzt eine Funktion zurück, die denselben Aufruf ausführt. Da sie ihn jedoch zurückgibt, kann die Auswertung später von außen erfolgen.

Mein Code lautet:

def bet(func):
    b = (lambda f: (lambda x: x(x))(lambda y:
          f(lambda *args: lambda: y(y)(*args))))(func)
    def wrapper(*args):
        out = b(*args)
        while callable(out):
            out = out()
        return out
    return wrapper

Die Funktion kann folgendermaßen verwendet werden: Hier sind zwei Beispiele mit schwanzrekursiven Versionen von Fakultät und Fibonacci:

>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55

Offensichtlich ist die Rekursionstiefe kein Problem mehr:

>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

Dies ist natürlich der einzige wirkliche Zweck der Funktion.

Mit dieser Optimierung kann nur eines nicht erreicht werden: Sie kann nicht mit einer rekursiven Endfunktion verwendet werden, die zu einer anderen Funktion ausgewertet wird (dies ergibt sich aus der Tatsache, dass aufrufbare zurückgegebene Objekte alle als weitere rekursive Aufrufe ohne Unterscheidung behandelt werden). Da ich normalerweise keine solche Funktion benötige, bin ich mit dem obigen Code sehr zufrieden. Um jedoch ein allgemeineres Modul bereitzustellen, habe ich etwas mehr darüber nachgedacht, um eine Problemumgehung für dieses Problem zu finden (siehe nächster Abschnitt).

In Bezug auf die Geschwindigkeit dieses Prozesses (was jedoch nicht das eigentliche Problem ist) ist er ziemlich gut. Schwanzrekursive Funktionen werden sogar viel schneller als mit dem folgenden Code mit einfacheren Ausdrücken ausgewertet:

def bet1(func):
    def wrapper(*args):
        out = func(lambda *x: lambda: x)(*args)
        while callable(out):
            out = func(lambda *x: lambda: x)(*out())
        return out
    return wrapper

Ich denke, dass die Bewertung eines Ausdrucks, auch wenn er kompliziert ist, viel schneller ist als die Bewertung mehrerer einfacher Ausdrücke, was in dieser zweiten Version der Fall ist. Ich habe diese neue Funktion nicht in meinem Modul behalten, und ich sehe keine Umstände, unter denen sie anstelle der "offiziellen" verwendet werden könnte.

Fortsetzung übergeben Stil mit Ausnahmen

Hier ist eine allgemeinere Funktion; Es ist in der Lage, alle rekursiven Funktionen zu verarbeiten, einschließlich derjenigen, die andere Funktionen zurückgeben. Rekursive Aufrufe werden mithilfe von Ausnahmen von anderen Rückgabewerten erkannt. Diese Lösung ist langsamer als die vorherige; Ein schnellerer Code könnte wahrscheinlich geschrieben werden, indem einige spezielle Werte als "Flags" verwendet werden, die in der Hauptschleife erkannt werden, aber ich mag die Idee, spezielle Werte oder interne Schlüsselwörter zu verwenden, nicht. Es gibt eine lustige Interpretation der Verwendung von Ausnahmen: Wenn Python keine rekursiven Aufrufe mag, sollte eine Ausnahme ausgelöst werden, wenn ein rekursiver Aufruf auftritt, und die pythonische Methode besteht darin, die Ausnahme abzufangen, um eine saubere zu finden Lösung, was eigentlich hier passiert ...

class _RecursiveCall(Exception):
  def __init__(self, *args):
    self.args = args
def _recursiveCallback(*args):
  raise _RecursiveCall(*args)
def bet0(func):
    def wrapper(*args):
        while True:
          try:
            return func(_recursiveCallback)(*args)
          except _RecursiveCall as e:
            args = e.args
    return wrapper

Jetzt können alle Funktionen verwendet werden. Im folgenden Beispiel f(n)wird die Identitätsfunktion für jeden positiven Wert von n ausgewertet:

>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Natürlich könnte argumentiert werden, dass Ausnahmen nicht dazu gedacht sind, den Interpreter absichtlich umzuleiten (als eine Art gotoAussage oder wahrscheinlich eher als eine Art Weitergabestil), was ich zugeben muss. Aber auch hier finde ich die Idee, tryeine einzelne Zeile als returnAnweisung zu verwenden , lustig : Wir versuchen, etwas zurückzugeben (normales Verhalten), können dies jedoch aufgrund eines rekursiven Aufrufs (Ausnahme) nicht tun.

Erste Antwort (29.08.2013).

Ich habe ein sehr kleines Plugin für die Behandlung der Schwanzrekursion geschrieben. Sie finden es möglicherweise mit meinen Erklärungen dort: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Es kann eine Lambda-Funktion, die mit einem Schwanzrekursionsstil geschrieben wurde, in eine andere Funktion einbetten, die sie als Schleife auswertet.

Das interessanteste Merkmal dieser kleinen Funktion ist meiner bescheidenen Meinung nach, dass die Funktion nicht auf einem schmutzigen Programmier-Hack beruht, sondern auf einem bloßen Lambda-Kalkül: Das Verhalten der Funktion wird beim Einfügen in eine andere Lambda-Funktion in ein anderes geändert sieht dem Y-Kombinator sehr ähnlich.

Das Wort von Guido ist unter http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Ich habe kürzlich in meinem Python-Verlaufsblog einen Eintrag über die Ursprünge der Funktionsfunktionen von Python veröffentlicht. Eine Nebenbemerkung über die Nichtunterstützung der Tail Recursion Elimination (TRE) löste sofort mehrere Kommentare darüber aus, wie schade, dass Python dies nicht tut, einschließlich Links zu aktuellen Blogeinträgen anderer, die versuchen, zu "beweisen", dass TRE zu Python hinzugefügt werden kann leicht. Lassen Sie mich also meine Position verteidigen (das heißt, ich möchte kein TRE in der Sprache). Wenn Sie eine kurze Antwort wünschen, ist sie einfach unpythonisch. Hier ist die lange Antwort:

CPython unterstützt und wird wahrscheinlich niemals die Tail-Call-Optimierung unterstützen, die auf den Aussagen von Guido van Rossum zu diesem Thema basiert .

Ich habe Argumente gehört, die das Debuggen erschweren, weil es den Stack-Trace modifiziert.

Probieren Sie die experimentelle Makropy- TCO-Implementierung für die Größe aus.

Neben der Optimierung der Schwanzrekursion können Sie die Rekursionstiefe manuell einstellen, indem Sie:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))