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!