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

在设计递归函数时,必须满足两个条件:调用自身、有结束条件。下面我们以 “用递归方式求 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个月后共有多少对兔子?

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/73