python/school/_out_of_subset/076.py · 1800 字节 · 下载原文
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.__name__ = func.__name__
wrap.__doc__ = func.__doc__
return wrap
def climbStairs1(n):
#递推法
a = 1
b = 2
c = 4
for i in range(n-3):
c, b, a = a+b+c, c, b
return c
def climbStairs2(n):
#递归法
first3 = {1:1, 2:2, 3:4}
if n in first3.keys():
return first3[n]
else:
return climbStairs2(n-1) + \
climbStairs2(n-2) + \
climbStairs2(n-3)
@tail_call_optimized
def climbStairs3(n, a=1, b=2, c=4):
# 尾递归
if n == 3:
return c
return climbStairs3(n-1, b, c, a+b+c)
def climbStairs4(n):
# 嵌套函数定义+生成器函数实现尾递归优化
def nested(n, a=1, b=2, c=4):
# 尾递归
if n == 3:
yield c
yield nested(n-1, b, c, a+b+c)
import types
g = nested(n)
while isinstance(g, types.GeneratorType):
g = next(g)
return g
n = 1350
for func in (climbStairs1, climbStairs3, climbStairs4, climbStairs2):
start = time()
print(func.__name__, func(n), time()-start)