递归理解（未完）

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个t台阶，请问n个台阶有多少种走法？

第一步走了一个台阶或第一步走了两个台阶，到下一个台阶也是类似，故这是一个递归。

n个台阶就是，走了一个台阶后加剩下n-1台阶的走法，走了两个台阶后剩下n-2台阶的走法，

f(n)=f(n-1)+f(n-2)

终止条件：只剩一个台阶一种走法，只剩两个台阶两种走法，

f(1)=1，f(2)=2

def fun(n):
    if(n == 1): return 1

    elif (n == 2): return 2

    else:
        return fun(n - 1) + fun(n - 2)

缺点：堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等

防止递归造成堆栈溢出，加入深度，大于1000就不再溢出

depth=0
def fun(n):
    global depth
    depth+=1
    print('depth=',depth)
    if (depth>1000): return -1
    if(n == 1): return 1

    elif (n == 2): return 2

    else:
        return fun(n - 1) + fun(n - 2)
print(fun(3))

重复计算：