python尾递归优化问题

在思否上面看到了这样一篇的文章:讲述了如何去除python对递归的限制,看完后不得不对他佩服,不过仔细想想也是挺合理的!他主要是通过抛出异常来结束之前的栈然后新开栈来调用函数,具体代码如下:

#!/usr/bin/env python3.5
# 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(Exception):
    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(2000))

具体原理:
当递归函数被该装饰器修饰后, 递归调用在装饰器while循环内部进行, 每当产生新的递归调用栈帧时: f.f_back.f_back.f_code == f.f_code:, 就捕获当前尾调用函数的参数, 并抛出异常, 从而销毁递归栈并使用捕获的参数手动调用递归函数. 所以递归的过程中始终只存在一个栈帧对象, 达到优化的目的.

不过这种企业需求真的很少!在python中递归深度最大是950+次(具体多少次真的不好说,不同的机子和平台不一样的!而且同一台机子的不同执行时间也不一样!这里就不去探究他!但是一定小于999次)

思否原文连接https://segmentfault.com/a/1190000007641519

关于尾递归: 当递归调用是函数体中最后执行的语句并且它的返回值不属于表达式一部分时， 这个递归就是尾递归。

现代的编译器就会发现这个特点， 生成优化的代码， 复用栈帧。斐波那契数列算法中因为有个n * factorial(n-1) , 虽然也是递归，但是递归的结果处于一个表达式中，还要做计算， 所以就没法复用栈帧了，只能一层一层的调用下去。
虽然尾递归调用也会创建新的栈, 但是我们可以优化使得尾递归的每一级调用共用一个栈!

关于尾递归优化还有另外一种思路,那就是汉诺塔思路:
具体查看网址https://www.cnblogs.com/tgycoder/p/6063722.html

相对于上面的算法,汉诺塔思路会更加好!但是汉诺塔思路设计的东西不会无限递归,虽然他和上面的抛出异常的方式都是尾递归的每一级调用共用一个栈,但是抛出异常的方式利用了cpython的机制 "漏洞" 来实现自己无限递归的运作方式!但是汉诺塔思路没利用!

其中一种尾递归优化的方式其实就是建立在汉诺塔的思路上面的!比如下面的代码:

def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n-1, total+n)##这一步必须没有表达式,而是只有call本身函数

print(tail_recursion(993))##但是还是受到了cpython解释器的限制!这里把993更改
                          ##为999会发现抛出递归最大深度的异常