1.7.递归函数
\(1.7\)递归函数
一、递归函数的概念与分类
1.概念
如果函数体直接或间接调用函数本身，则函数称为递归函数。也就是说，执行递归函数体的过程可能反过来又需要再次应用该函数。
2.递归的原理
一般的递归由以下结构构成：
- 基本情况：当递归函数递归到一个或多个基本情况时，函数将直接返回某个值，跳出递归
- 递归调用：随着递归调用，问题逐渐得到简化
以阶乘的求解为例： 1
2
3
4
5
6
7def fact(n):
if n==0:
return 1
elif n==1:
return 1
else:
return n*f(n-1)
当递归通过递归函数的连续调用“展开”到越来越简单的问题时，结果最终会从基本情况开始构建。递归结束时将参数\(1\)传递给\(fact\); 每个调用的结果取决于下一个调用，直到达到基本情况。
在我们利用以上计算模型得出递归的最终结果时，也可将递归调用看作函数抽象。在阶乘中，我们不关心\(fact(n-1)\)是怎么计算出来的，我们应该简单地相信它计算的是\(n-1\)的阶乘。这种对递归函数的看法被称作\(recursive\;leap\;of\;faith\)，即我们相信递归调用简单情况时函数会得出正确结果，在这个认知的基础上去计算复杂情况。例如计算阶乘时，我们相信\(fact(n-1)\)能正确计算出\((n-1)!\)，只需检查\(n!\)在这个假设成立下是否能得到正确计算。通过这种方式，验证递归函数的正确性是一种数学归纳法。
3.递归与循环函数的区别
我们以阶乘函数的循环写法为例： 1
2
3
4
5def fact_iter(n):
total, k = 1, 1
while k <= n:
total, k = total * k, k + 1
return total
我们从两个角度看待它们的区别：
\(a.\)实现方式：
阶乘的循环写法是通过逐项相乘实现的，而阶乘的递归写法是通过当前项\(fact(n)\)与前一项\(fact(n-1)\)的关系实现的。
\(b.\)调用参数
阶乘的循环写法需要调用两个额外参数\(total,k\)，而递归则没有这两个参数。在递归中，\(fact(n)\)本身的返回值及相当于循环中的\(total\)，而\(n\)则用来隐式地跟踪\(n!\)计算到哪一步，相当于循环中的\(k\)。
二、相互递归调用
1.概念
当一个递归过程分为两个相互调用的函数时，这两个函数被称为相互递归的。
对于多主体的问题，利用相互递归调用可以得到很完美的解决。
2.实例讲解
\(e.g.1.\)考虑如下所述对于奇偶的定义：
- \(0\)为偶数
- 若\(n-1\)为偶数，则\(n\)为奇数
- 若\(n-1\)为奇数，则\(n\)为偶数
1
2
3
4
5
6
7
8
9def is_even(n):
if(n==0):
return True
return is_odd(n-1)
def is_odd(n):
if(n==0):
return False
return is_even(n-1)
\(p.s.\)通过打破两个函数之间的抽象边界，可以将相互递归的函数转换为单个递归函数。如上述函数可如下改写：
1
2
3
4
5
6
7
8def is_even(n):
if n == 0:
return True
else:
if (n-1) == 0:
return False
else:
return is_even((n-1)-1)
\(e.g.2.\)考虑一个两人博弈，在这个博弈中，一张桌子上有 \(n\)个初始卵石。玩家轮流从桌子上移走一个或两个鹅卵石，移走最后一个鹅卵石的玩家获胜。假设爱丽丝和鲍勃玩这个游戏，每个人都使用一个简单的策略:
- 爱丽丝总是拿走一块鹅卵石
- 如果桌子上的鹅卵石数量是偶数，那么鲍勃就会移除两个鹅卵石，另一个是偶数
给定\(n\)个最初的卵石和爱丽丝开始，谁赢得了比赛？
\(solve\)：这里爱丽丝与鲍勃是不同主体，分设为两个函数即可：
1
2
3
4
5
6
7
8
9
10
11def alice(n):
if(n==0):
print("Bob wins")
else:
return bob(n-1)
def bob(n):
if(n==0):
print("Alice wins")
else:
return alice(n-1)
三、树形递归
1.树形递归的概念
树形递归是一种常用的递归，在树形递归中，递归函数被调用不止一次。
我们以斐波那契数列的递归求解为例： 1
2
3
4
5
6
7def fib(n):
if n == 1:
return 0
if n == 2:
return 1
else:
return fib(n-2) + fib(n-1)
可以看到，递归的写法与斐波那契的定义\(Fib_n=Fib_{n-1}+Fib_{n-2}\)是完全契合的。
2.实例讲解
\(e.g.1.\)将\(n\)分解为某个单调递增的序列，且序列中数的最大值不超过\(m\)。给出\(n,m\)，求出满足条件序列的数量。
\(solve\)：我们考虑下面两件事：
分组方法：为了保证不重不漏，我们从序列中最大值\(m\)入手，可分为以下情况：
- 选一个\(m\)，然后对\(n-m\)执行相同操作
- 不选\(m\)，此时序列中最大值变为\(m-1\)，然后继续执行相同操作
基本情况：
n==0：\(return 1\)n<0：\(return 0\)m==0：\(return 0\)
于是可写出如下代码： 1
2
3
4
5
6
7
8def div(n,m):
if n==0:
return 1
if n<0:
return 0
if m==0:
return 0
return div(n-m,m)+div(n,m-1)