Hier verwenden wir die typische Fibonacci-Sequenz als Beispiel, um zu zeigen, wie Dekoratoren zur Optimierung der Schwanzrekursion in Python verwendet werden. Freunde in Not können sich auf
Einführung in die Schwanzrekursion
Tail-Rekursion bedeutet, dass die letzte von der Funktion zurückgegebene Operation ein rekursiver Aufruf ist und die Funktion dann tail-rekursiv ist. Rekursion ist linear. Jedes Mal, wenn die Fakultätsfunktion aufgerufen wird, wird ein neuer Stapel (Last-In-First-Out) erstellt, indem der Stapel kontinuierlich verschoben wird, was leicht zu einem Stapelüberlauf führen kann. Die Schwanzrekursion nutzt den aktuellen Stapel, um rekursive Funktionen durch Datenabdeckung zu optimieren.
Die Fakultätsfunktion „Fakultät“ schließt die Schwanzrekursion ab, indem sie den berechneten Wert übergibt. Allerdings erlaubt Python dem Compiler nicht, die Schwanzrekursion zu optimieren. Wenn die Rekursion also mehrmals wiederholt wird, wird immer noch ein Fehler gemeldet (zu Lernzwecken).
def factorial(n, x):
if n == 0:
return x
else:
return factorial(n-1, n*x)
print factorial(5, 1) # 120Tail Recursive Optimization wird hier verwendet Als Beispiel wird der lineare rekursive Algorithmus verwendet, weil er zu ineffizient war. Schauen wir uns zunächst die Tail-Pass-Aufrufmethode an:
(n,b1=1,b2=1,c=3): if n<3: return 1 else: if n==c: return b1+b2 else: return Fib(n,b1=b2,b2=b1+b2,c=c+1)
>>> def Fib(n,b1=1,b2=1,c=3): ... if n<3: ... return 1 ... else: ... if n==c: ... return b1+b2 ... else: ... return Fib(n,b1=b2,b2=b1+b2,c=c+1) ... >>> Fib(1001) 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L >>>
..... File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib File "<stdin>", line 8, in Fib RuntimeError: maximum recursion depth exceeded >>>
@tail_call_optimized def Fib(n,b1=1,b2=1,c=3): if n<3: return 1 else: if n==c: return b1+b2 else: return Fib(n,b1=b2,b2=b1+b2,c=c+1)
Nun, es ist dieser @tail_call_optimized-Dekorator, dieser Dekorator macht Python magisch Es durchbricht die Grenze des Aufrufstapels.
class TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargs def tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func
