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)