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)