"""
函数的递归调用：一个函数直接或间接的调用了自身
使用递归调用可以把复杂的程序写得比较简单，写递归函数有两个要点：
1. 递归公式：第N次和第N-1次调用之间的关系
2. 收敛条件：什么时候停止递归调用，无限制的递归调用会引发RecursionError
"""
from functools import lru_cache


# 计算斐波拉切数
# 使用缓存装饰器缓存函数执行的中间结果
# 通过空间换时间的方式来优化程序的性能！！！
@lru_cache()
def fib(n):
    if n in (1, 2):
        return 1
    return fib(n - 1) + fib(n - 2)


# def fib(n):
#     a, b = 0, 1
#     for _ in range(n):
#         a, b = b, a + b
#     return a


# for num in range(1, 121):
#     print(num, fib(num))


# 计算n的阶乘：n! = n * (n - 1)!
def fac(n):
    if n in (0, 1):
        return 1
    return n * fac(n - 1)


# 5 * fac(4)
#     4 * fac(3)
#         3 * fac(2)
#             2 * fac(1)
#                 1
# print(fac(5))


# 一个小孩爬楼梯，一次可以爬1个台阶、2个台阶或3个台阶，问爬完10个台阶有多少种走法
# @lru_cache()
# def climb(n):
#     if n < 0:
#         return 0
#     elif n == 0:
#         return 1
#     return climb(n - 1) + climb(n - 2) + climb(n - 3)


def climb(n):
    a, b, c = 1, 2, 4
    for _ in range(n - 1):
        a, b, c = b, c, a + b + c
    return a


for num in range(1, 101):
    print(num, climb(num))