← 都来码 / Dolaima← 例程索引python/school/_out_of_subset/077.py 原文

python/school/_out_of_subset/077.py · 1159 字节 · 下载原文

from time import time
import sys

class TailRecurseException(BaseException):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs
        
def tail_call_optimized(func):
    def wrap(*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 True:
                try:
                    # 使用修改后的参数
                    return func(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs
    wrap.__doc__ = func.__doc__ 
    return wrap

@tail_call_optimized
def tailFib(n, temp=0, result=1):
    # 尾递归,用迭代的思路去理解
    if n == 1:
        return result
    return tailFib(n-1, result, temp+result)

n = 2300
start = time()
print('tailFib:', tailFib(n), time()-start)

def fib(n):
    a, b = 1, 1
    for i in range(n-2):
        a, b = b, a+b
    return b
start = time()
print('    fib:', fib(n), time()-start)