递归算法和斐波拉契数列

编程语言中，我们习惯将函数（方法）调用自身的过程称为递归，调用自身的函数称为递归函数，用递归方式解决问题的算法称为递归算法。

在设计递归函数时，必须满足两个条件：调用自身、有结束条件。下面我们以 “用递归方式求 n!” 的问题为例，来写一个递归函数。

def func(n):
   if n == 1:  # 结束条件
       return 1
   else:  # 调用自身
       return n * func(n - 1)

print(func(4))  # 输出24

除了求 n! 外，递归算法还可以解决斐波那契数列问题，很多算法也都需要借助递归实现，后续会给大家一一进行讲解。

斐波那契数列

公元1202年，意大利数学家莱昂纳多·斐波那契提出了具备以下特征的数列：

1) 前两个数的值分别为 0 、1 或者 1、1；

2) 从第 3 个数字开始，它的值是前两个数字的和；

为了纪念他，人们将满足以上两个特征的数列称为斐波那契数列。公示表示：f(n) = f(n-1) + f(n-2)

如下就是一个斐波那契数列：

1 1 2 3 5 8 13 21 34 ......

def fib(n):
   if n == 1 or n==2:
       return 1
   else:
       return fib(n-1) + fib(n-2)

for i in range(1, 10):
   print(fib(i), end=' ')

虽然递归能直观地实现斐波拉契数列，但效率很低，这和递归的底层实现机制有关，可以参考递归原理。以下再给出不用递归实现的斐波拉契数列代码。

def fib(n):
   num1 = 1
   num2 = 1
   lst = []
   for i in range(1, n+1):
       lst.append(num1)
       next = num1+num2
       num1 = num2
       num2 = next
   return lst

print(fib(9))

另外，斐波拉契问题还有很多变种问题，有兴趣的可以继续研究，比如：

上楼梯问题：有一楼梯共n级，若每次只能跨一级或者二级，共有多少走法？

兔子问题：假定一对大兔子每月能生一对小兔子，且每对新生的小兔子经过一个月可以长成一对大兔子，才具备繁殖能力，不考虑死亡，且每次均生下一雌一雄，问n个月后共有多少对兔子？