大家都知道递归是非常消耗资源的,也就是非常消耗内存。所以往往递归深度非常深的时候,会抛出一个异常(stack overflow)。所以对于递归,又产生了一种尾递归

什么是尾递归

先说尾调用,尾调用就是函数调用自身,称为递归。如果尾调用自身,就称为尾递归。

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

第一种不属于尾递归,因为在函数的最后并没有只调用自己,而是有个乘法,第二种则是尾递归,在函数的最后仅仅调用自己。通常尾递归需要对函数进行一定改写。

对于尾递归来说,每次只存在一个调用记录,不需要保存上次递归产生的参数等,所以永远不会发生"栈溢出"错误。

python 尾递归

很多语言对于尾递归都有专门的优化,但是python对于尾递归是没有优化的,一般会通过迭代进行优化,不过我无意看到一篇文章,通过装饰器来优化尾递归

话不多说,先放代码:

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 as 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))

我们先看如果不用尾递归优化,stack的调用是怎么样的

会发现随着递归深度的上升,stack也随之增长。

我们看通过装饰器优化过后的尾递归stack的调用情况。

通过给factorial函数加上tail_call_optimized的装饰器,当函数开始运行时,首先会执行装饰器中的func函数,传入args=10000的参数,因为不满足if条件(if条件主要是来判断是否产生了一个新栈),所以进入while,while中调用了g函数,因为装饰器的原因,这里执行g函数,其实是执行了factorial函数,发现不满足递归跳出条件n==0,所以执行到facorial(n-1,n×acc),这时继续执行装饰器的func函数,此时满足if条件的判断,抛出TailRecurseException异常,这个异常类拿到了此时factorial的所有参数,因为碰到了异常,所有factorial(n-1,nxacc)这个函数return 异常以及保存的参数,这时候新产生的栈由于异常的产生所以被销毁,又因为这个factorial其实是调用在装饰器里的g函数,所以同样将异常和保存的参数返回给装饰器里的g函数,函数继续执行,碰到了捕获异常的exception,进入捕获逻辑的操作,将参数保存传入下一次的g中,这里的g函数均为手动调用,所以体现了原作者的强大

接下来依次执行上述逻辑,知道到达递归出口,返回最后的结果acc

结合流程图一块食用,效果更佳

不得不说大佬就是大佬
!{跪地}(http://47.103.203.6/wp-content/uploads/2019/05/YSEDWHCRYFAEV99C_5J-1.jpg)

参考

https://segmentfault.com/a/1190000007641519

推荐阅读

sys._getframe([depth])各个参数含义

版权声明:本文为原创文章,版权归 heroyf 所有。
本文链接: https://heroyf.club/2019/05/tail_recursion/


“苹果是给那些为了爱选择死亡的人的奖励”