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

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)