Python开启尾递归优化!

junnplus 发布于2019-07-31 10:54 / 591人阅读

摘要：尾递归优化一般递归与尾递归一般递归执行可以看到一般递归每一级递归都产生了新的局部变量必须创建新的调用栈随着递归深度的增加创建的栈越来越多造成爆栈尾递归尾递归基于函数的尾调用每一级调用直接返回递归函数更新调用栈没有新局部变量的产生类似迭代的

Python尾递归优化 一般递归与尾递归 一般递归:

def normal_recursion(n):
    if n == 1:
        return 1
    else:
        return n + normal_recursion(n-1)

执行：

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 + 3
5 + 4 + 6
5 + 10
15

可以看到, 一般递归, 每一级递归都产生了新的局部变量, 必须创建新的调用栈, 随着递归深度的增加, 创建的栈越来越多, 造成爆栈?

尾递归

尾递归基于函数的尾调用, 每一级调用直接返回递归函数更新调用栈, 没有新局部变量的产生, 类似迭代的实现:

def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n-1, total+n)

执行：

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

可以看到, 尾递归每一级递归函数的调用变成"线性"的形式. 这时, 我们可以思考, 虽然尾递归调用也会创建新的栈, 但是我们可以优化使得尾递归的每一级调用共用一个栈!, 如此便可解决爆栈和递归深度限制的问题!

C中尾递归的优化

gcc使用-O2参数开启尾递归优化:

int tail_recursion(int n, int total) {
    if (n == 0) {
        return total;
    }
    else {
        return tail_recursion(n-1, total+n);
    }
}

int main(void) {
    int total = 0, n = 4;
    tail_recursion(n, total);
    return 0;
}

反汇编

$ gcc -S tail_recursion.c -o normal_recursion.S
$ gcc -S -O2 tail_recursion.c -o tail_recursion.S gcc开启尾递归优化

对比反汇编代码如下(AT&T语法, 左图为优化后)

可以看到, 开启尾递归优化前, 使用call调用函数, 创建了新的调用栈(LBB0_3); 而开启尾递归优化后, 就没有新的调用栈生成了, 而是直接pop bp指向的_tail_recursion函数的地址(pushq %rbp)然后返回, 仍旧用的是同一个调用栈!

Python开启尾递归优化

cpython本身不支持尾递归优化, 但是一个牛人想出的解决办法：实现一个 tail_call_optimized 装饰器

#!/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 sys

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

@tail_call_optimized
def factorial(n, acc=1):
    "calculate a factorial"
    if n == 0:
        return acc
    return factorial(n-1, n*acc)

print factorial(10000)

这里解释一下sys._getframe()函数:

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.

即返回depth深度调用的栈帧对象.

import sys

def get_cur_info():
    print sys._getframe().f_code.co_filename  # 当前文件名
    print sys._getframe().f_code.co_name  # 当前函数名
    print sys._getframe().f_lineno # 当前行号
    print sys._getframe().f_back # 调用者的帧

更多关于sys._getframe的使用请看Frame Hacks
说一下tail_call_optimized实现尾递归优化的原理: 当递归函数被该装饰器修饰后, 递归调用在装饰器while循环内部进行, 每当产生新的递归调用栈帧时: f.f_back.f_back.f_code == f.f_code:, 就捕获当前尾调用函数的参数, 并抛出异常, 从而销毁递归栈并使用捕获的参数手动调用递归函数. 所以递归的过程中始终只存在一个栈帧对象, 达到优化的目的.
为了更清晰的展示开启尾递归优化前、后调用栈的变化和tail_call_optimized装饰器抛异常退出递归调用栈的作用, 我这里利用pudb调试工具做了动图:

开启尾递归优化前的调用栈

开启尾递归优化后(tail_call_optimized装饰器)的调用栈

通过pudb右边栏的stack, 可以很清晰的看到调用栈的变化.
因为实现了尾递归优化, 所以factorial(10000)都不害怕递归深度限制报错啦!

云服务器 GPU云服务器优化递归数据栈 python递归错误 python递归例子 python递归调用

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44328.html

js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
用 JavaScript 实现链表操作 - 08 Remove Duplicates

摘要：递归版本尾递归很多递归没办法自然的写成尾递归，本质原因是无法在多次递归过程中维护共有的变量，这也是循环的优势所在。这是因为虽然用的，但并没有开启尾递归优化。 TL;DR 为一个已排序的链表去重，考虑到很长的链表，需要尾调用优化。系列目录见前言和目录。需求实现一个 removeDuplicates() 函数，给定一个升序排列过的链表，去除链表中重复的元素，并返回修改后的链表。理想...

Me_Kun 2019-08-21 15:04 评论0 收藏0
小李飞刀：python你慢点飞，我的脑子还在后面追

摘要：默认参数设置默认参数时，有几点要注意一是必选参数在前，默认参数在后，否则的解释器会报错二是如何设置默认参数。注意此处，获得的其实是的拷贝，函数内对的改变不会影响到。使用递归函数需要注意防止栈溢出。总是在最前面的叨逼叨最近总是在想成长这两个很常常被提起的事情，这对于一个已经25岁的半中年而言，已经是一个不太能高频提起的词。但是，最近一些事情吧，总让我觉得我的生长期似乎比正常人来的晚了...

kevin 2019-07-30 18:40 评论0 收藏0
Python笔记

摘要：针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。 python 头部： #!/usr/bin/env python # -*- coding: utf-8 -*- 函数的参数 Python的函数具有非常灵活的参数形态，既可以实现简单的调用，又可以传入...

yuxue 2019-07-31 10:07 评论0 收藏0
【数据科学系统学习】Python # 编程基础[一]

摘要：在定义函数时给定的名称称作形参，在调用函数时你所提供给函数的值称作实参。调用函数要调用一个函数，需要知道函数的名称和参数。默认参数值可以有效帮助解决这一情况。是默认参数定义默认参数要牢记一点默认参数必须指向不变对象。关于数据科学在做什么，我们已经在前两篇文章中进行了总结，即专题概述和描述性统计分析。要进行数据科学的探索，需要一个好工具，就是Python。从本篇开始，将总结学习Pyth...

luckyyulin 2019-07-30 17:21 评论0 收藏0