台阶问题

问题

你要上一段楼梯，每次只能上一步或两步，对于n级台阶，一共有多少种上台阶的方法

## 分析 加入我们知道走到n-2级和n-1级台阶有多少种方法，那么我们就知道走到n级台阶有多少种方法 ```python f(n) = f(n-1) + f(n-2)

看到这里，大家应该就知道了可以使用递归来解决这个问题，那么递归的出口在哪里呢，对于1级台阶，f(1)=1，对于2级台阶，f(2)=2，因此我们得到呢递归的出口
```python
f(1) = 1
f(2) = 2

## 实现 ```python def func(n): if n == 1: return 1 if n == 2: return 2 else: return func(n-1) + func(n-2)

给此函数加一个装饰器，计算函数递归调用的次数
```python
def call_num(func):
    """
    此装饰器函数用于计算函数调用次数
    :param func:
    :return:
    """
    num = 0

    def inner(*args, **kwargs):
        nonlocal num
        ret = func(*args, **kwargs)
        num += 1
        print("function called number:", num)
        return ret
    return inner


@call_num
def func(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    else:
        return func(n-1) + func(n-2)

print(func(30))

运行结果

function called number: 1664079
1346269

当n=30时，递归次数居然高达1664079次！