递归函数

1.递归函数：在函数的声明中调用函数本身
这儿的func1就是一个递归函数

 def func1()
    print('aaa')
    func1()
  func()

2.递归作用：理论上循环能够做到的事情递归都可以做到（但实际上一般不用递归。除非非用不可）
3.步骤
递归函数：f(n)
a.确定临界值（结束函数的时刻或者结束递归的条件）
b.假设函数的功能已经实现，然后找到f(n)和f(n-1)关系
c.使用f(n-1）与f(n)的关系去实现f(n)的功能
计算1+2+3+4+ ...+n
方法1:使用循环

def add(n):
  sum1 = 0
for x in range(1,n+1):
    sum1 += x
return sum1

方法2：使用递归函数

def add(n):
    if n == 1:
        return 1
  #  确定临界值
  # 假设函数功能已经实现
  # add(n-1) = 1+2+3+...+n-1
  # add(n) = 1+ 2+3+...+n-1+n = add(n-1) + n
  # 通过add(n-1) 去实现add(n)的功能
  return add(n-1) +n
print(add(100))

思考：虽然两种方法的结果一样，但是第二种方法在程序计算的过程中重复了很多次相同的计算，所以这不是一个好的算法
解决方法：

def add(n,m=1):
   if n == 1:
        return m 
return add(n-1, n+m)

总结: 递归要慎用！（能用循环做的，就不要用递归。递归消耗内存也消耗CPU资源）

爬楼梯问题
小明爬楼梯，有时候一次爬1层，有时候一次爬2层，有时候一次爬3层，如果有10层楼梯，小明总共有多少种爬楼梯的方法？