Home > Article > Backend Development > Using decorators to optimize tail recursion in Python
Here we use the typical Fibonacci sequence as an example to show examples of using decorators to optimize tail recursion in Python. Friends in need can refer to
Introduction to Tail Recursion
Tail recursion is when the last operation returned by the function is a recursive call, then the function is tail recursive.
Recursion is linear. For example, every time the factorial function is called, a new stack (last-in-first-out) is created. Recursion is created by continuously pushing the stack, which can easily lead to stack overflow. Tail recursion uses the current stack to optimize the recursive function through data coverage.
The factorial function factorial completes tail recursion by passing the calculated value. However, python does not allow the compiler to optimize tail recursion, so if the recursion is repeated multiple times, an error will still be reported (for learning purposes).
eg:
def factorial(n, x): if n == 0: return x else: return factorial(n-1, n*x) print factorial(5, 1) # 120
Tail recursion optimization
Fibo is used here Let’s take the odd number as an example. The linear recursive algorithm was passed away because it was too inefficient. Let’s first look at the tail-pass method of calling:
(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)
Let’s test this program and call Fib(1001). The result is:
>>> 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 >>>
If we use Fib(1002), the result is the coffee table. , as follows:
..... 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 >>>
Okay, now we come to tail recursion optimization
We add a Decorator to the Fib function just now, as follows:
@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)
Well, it is this @tail_call_optimized decorator. This decorator allows Python to magically break the limitations of the call stack.
Now even if we use Fib (20000), we can still run the result in 780ms (780ms is the result of the 2,000 yuan netbook mentioned in the previous blog post)
It’s not a lie. Let's take a look at this magical code:
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
The method used has been shown before. What is eye-opening to me is that, The author used the method of throwing exceptions and catching them himself to break the growth of the call stack, which is simply incredible. Moreover, efficiency issues cause about five times the time overhead compared to direct tail recursion Fib.
In the end, surprisingly, the goal of tail recursion optimization was achieved.
For more articles related to using decorators to optimize tail recursion in Python, please pay attention to the PHP Chinese website!