Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to open tail recursive optimization in Python". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to turn on tail recursive optimization in Python".

General Recursion and tail Recursion General Recursion: def normal_recursion (n): if n = = 1: return 1 else: return n + normal_recursion (nMel 1)

Execute:

Normal_recursion (5) 5 + normal_recursion (4) 5 + 4 + normal_recursion (3) 5 + 4 + 3 + normal_recursion (2) 5 + 4 + 3 + 2 + normal_recursion (1) 5 + 4 + 3 + 35 + 4 + 65 + 1015

As you can see, general recursion, each level of recursion produces new local variables, and a new call stack must be created. With the increase of the depth of recursion, more and more stacks are created, resulting in a stack explosion.

Tail recursion

Tail recursion is based on the tail call of the function. Each level call directly returns the recursive function to update the call stack, without the generation of new local variables, similar to the implementation of iteration:

Def tail_recursion (n, total=0): if n = 0: return total else: return tail_recursion (NMur1, total+n)

Execute:

Tail_recursion (5,0) tail_recursion (4,5) tail_recursion (3,9) tail_recursion (2,12) tail_recursion (1,14) tail_recursion (0,15) 15

As you can see, the call to the recursive function at each level of tail recursion becomes linear. At this point, we can think that although tail recursive calls also create a new stack, we can optimize so that each level of tail recursion calls share a stack!, so that we can solve the problem of stack burst and recursive depth limit!

Optimization of tail Recursion in C

Gcc uses the-O2 parameter to enable tail recursive optimization:

Int tail_recursion (int n, int total) {if (n = = 0) {return total;} else {return tail_recursion (n int total 1, total+n);}} int main (void) {int total = 0, n = 4; tail_recursion (n, total); return 0;}

Disassembly

$gcc-S tail_recursion.c-o normal_recursion.S$ gcc-S-O2 tail_recursion.c-o tail_recursion.S gcc Open tail Recursive Optimization

The disassembly code is compared as follows (AT&T syntax, the picture on the left is optimized)

As you can see, before turning on tail recursive optimization, a new call stack (LBB0_3) is created by using call to call the function; after turning on tail recursive optimization, no new call stack is generated, but the address of the _ tail_recursion function pointed to by pop bp (pushq% rbp) is returned, still using the same call stack!

Python Open tail Recursive Optimization

Cpython itself does not support tail recursive optimization, but a great solution:

Implement a tail_call_optimized decorator

#! / usr/bin/env python2.4# This program shows off a python decorator (# which implements tail call optimization. It# does this by throwing an exception if it is# it's own grandparent, and catching such# exceptions to recall the stack.import sysclass TailRecurseException: def _ init__ (self, args, kwargs): self.args = args self.kwargs = kwargsdef 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: # throw exception raise TailRecurseException (args Kwargs) else: while 1: try: return g (* args, * * kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.qualified docking _ return func@tail_call_optimizeddef factorial (n Acc=1): "calculate a factorial" if n = 0: return acc return factorial (n*acc) print factorial (10000)

Here's an explanation of the sys._getframe () function:

Sys._getframe ([depth]):

Return a frame object from the call stack.

If optional integer depth is given, return the frame object that many calls below the top of the stack.

If that is deeper than the call stack, ValueEfror is raised. The default for depth is zero

Returning the frame at the top of the call stack.

That is, the stack frame object that returns the depth depth call.

Import sysdef get_cur_info (): print sys._getframe () .f_code.co_filename # current file name print sys._getframe () .f_code.co_name # current function name print sys._getframe () .f_lineno # current line number print sys._getframe () .f_back # the frame of the caller

For more information about the use of sys._getframe, see https://www.yisu.com/article/181387.htm.

Let's talk about the principle of tail recursive optimization with tail_call_optimized:

When the recursive function is modified by the decorator, the recursive call is made inside the while loop of the decorator. Whenever a new recursive call stack frame is generated: f.f_back.f_back.f_code = f. F. Call codeposition, the parameters of the current tail call function are captured and an exception is thrown, thus destroying the recursive stack and manually calling the recursive function with the captured parameters. Therefore, there is only one stack frame object in the process of recursion to achieve the purpose of optimization.

In order to more clearly show the changes of the call stack before and after opening the tail recursive optimization and the function of the tail_call_optimized decorator throwing an exception to exit the recursive call stack, I use the pudb debugging tool to make a dynamic diagram here:

Open the call stack before tail recursive optimization

Turn on the call stack after tail recursive optimization (tail_call_optimized decorator)

Through the stack in the right column of pudb, you can clearly see the change of the call stack.

Thank you for reading, the above is the content of "how to turn on tail recursive optimization of Python". After the study of this article, I believe you have a deeper understanding of how to turn on tail recursive optimization of Python, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.