python尾递归优化

参考 这里

 1class TailRecurseException(BaseException):
 2    def __init__(self, args, kwargs):
 3        self.args = args
 4        self.kwargs = kwargs
 5
 6
 7def tail_call_optimized(g):
 8    """
 9    This function decorates a function with tail call
10    optimization. It does this by throwing an exception
11    if it is it's own grandparent, and catching such
12    exceptions to fake the tail call optimization.
13
14    This function fails if the decorated
15    function recurses in a non-tail context.
16    """
17
18    def func(*args, **kwargs):
19        f = sys._getframe()
20        # 为什么是grandparent, 函数默认的第一层递归是父调用,
21        # 对于尾递归, 不希望产生新的函数调用(即:祖父调用),
22        # 所以这里抛出异常, 拿到参数, 退出被修饰函数的递归调用栈!(后面有动图分析)
23        if f.f_back and f.f_back.f_back \
24            and f.f_back.f_back.f_code == f.f_code:
25            # 抛出异常
26            raise TailRecurseException(args, kwargs)
27        else:
28            while 1:
29                try:
30                    return g(*args, **kwargs)
31                except TailRecurseException as e:
32                    # 捕获异常, 拿到参数, 退出被修饰函数的递归调用栈
33                    args = e.args
34                    kwargs = e.kwargs
35
36    func.__doc__ = g.__doc__
37    return func

测试

 1@tail_call_optimized
 2def factorial(n, acc=1):
 3    "calculate a factorial"
 4    from pudb import set_trace
 5    set_trace()
 6    if n == 0:
 7        return acc
 8    return factorial(n - 1, n + acc)
 9
10print factorial(10000)