外观
3.8 递归
求阶乘
从1一直乘到n,得到的数叫n的阶乘,记作n!。比如:
text
4! = 4 × 3 × 2 × 1 = 24换个看法。把后面三个数括起来:
text
4! = 4 × (3 × 2 × 1)
= 4 × 3!括号里正好是3!。要算4!,先算出3!,再乘4。
4!里藏着一个3!。3!里又藏着2!:3! = 3 × 2!。一直拆到1! = 1,不用再拆。
一个问题,用小一号的同一个问题来解决,这种做法叫递归。
学完这一节,你能看懂、写出简单的递归函数,一步一步跟出它是怎么算出结果的,并知道计算机怎样用栈执行递归。
先记住两个问题,这一节会回答:
本节问题用递归算4!,"同样的问题"一共要算几次?最先得出答案的是哪一个?
什么是递归
上一页的拆法写成式子,就是两行:
text
n! = n × (n-1)! 当 n 大于 1
1! = 1第一行用小一号的(n-1)!来算n!。第二行说,到1就停。
一个问题,用规模更小的同一个问题来解决,直到小到能直接给出答案,这就是递归。
这个定义有两个要点,逐条看。
规模变小:拆出来的问题,要比原来的小。n!拆出(n-1)!,4拆成3,再拆成2,越来越接近1。
text
n! = n × (n-1)! 4 → 3 → 2 → 1,越来越小
n! = n × n! 4 → 4 → 4 → …,一直在原地规模不变,就要一遍遍算同一个问题,永远算不完。
有出口:小到一定程度,要能直接给出答案,不再往下拆。这个地方叫递归的出口。n!的出口是1! = 1。
text
有出口: 4! → 3! → 2! → 1! = 1,停
没有出口: 4! → 3! → 2! → 1! → 0! → (-1)! → …没有出口,就会一直拆下去,停不下来。
两个要点缺一不可:规模变小,才能走到出口;有了出口,走到了才能停。
写成函数
C语言里,一个函数可以调用它自己。照着上一页的两行式子,就能写出算阶乘的函数:
c
int Fact(int n) {
if (n == 1) return 1; /* 出口:1! = 1 */
return n * Fact(n - 1); /* 规模变小:n! = n × (n-1)! */
}两行代码对着两行式子。
if (n == 1) return 1;就是1! = 1,是出口。
return n * Fact(n - 1);就是n! = n × (n-1)!。Fact在自己的函数体里调用了自己,参数从n变成n-1,规模变小。
调用自己的函数,叫递归函数。
试一试:
c
int main(void) {
for (int n = 1; n <= 5; n++)
printf("%d! = %d\n", n, Fact(n));
return 0;
}运行结果:
text
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120算阶乘,用循环也可以:
c
int f = 1;
for (int i = 2; i <= n; i++) f = f * i;两种写法都对。递归的好处是照着定义直接写:式子是什么样,代码就是什么样,不用另想"从几乘到几"。有的问题用递归说得很自然,用循环反而难写,第5章的树就是这样。
int 只装得下 12!
13!是6227020800,超过了int能表示的最大值,大约21亿。算出来会是一个错的数。
递和归
跟着Fact(4)走一遍,看它是怎么算出24的。
Fact(4)要算4 × Fact(3)。Fact(3)还没有结果,Fact(4)只能停在这里等。
Fact(3)要算3 × Fact(2),也停下来等。
Fact(2)要算2 × Fact(1),也停下来等。
Fact(1)碰到出口,直接得出1。
这一路往下调用,叫递:
text
Fact(4) = 4 × Fact(3) 等着
Fact(3) = 3 × Fact(2) 等着
Fact(2) = 2 × Fact(1) 等着
Fact(1) = 1 出口Fact(1)返回1。Fact(2)终于能算了:2 × 1 = 2,返回2。
Fact(3)接着算:3 × 2 = 6,返回6。
Fact(4)最后算:4 × 6 = 24,返回24。
这一路带着结果往回走,叫归:
text
Fact(1) = 1
Fact(2) = 2 × 1 = 2
Fact(3) = 3 × 2 = 6
Fact(4) = 4 × 6 = 24验算一下:4! = 4 × 3 × 2 × 1 = 24,对上了。Fact(3)也一样:递到Fact(1),再归回来,依次得出1、2、6。
回到开头的两个问题。
同样的问题一共算了4次:Fact(4)、Fact(3)、Fact(2)、Fact(1),就是4!、3!、2!、1!各算一次。
最先得出答案的是Fact(1),也就是1!。它是出口,不用等别人。
让程序自己报告一下。在Fact里加两句打印:
c
int Fact(int n) {
printf("进入 Fact(%d)\n", n);
if (n == 1) {
printf("Fact(1) 返回 1\n");
return 1;
}
int r = n * Fact(n - 1);
printf("Fact(%d) 返回 %d\n", n, r);
return r;
}printf("结果:%d\n", Fact(4));的运行结果:
text
进入 Fact(4)
进入 Fact(3)
进入 Fact(2)
进入 Fact(1)
Fact(1) 返回 1
Fact(2) 返回 2
Fact(3) 返回 6
Fact(4) 返回 24
结果:24看进入和返回的顺序:最后进入的Fact(1)最先返回,最先进入的Fact(4)最后返回。
用栈看递归
Fact(4)执行到最深处时,同时有4个n:4、3、2、1。名字都叫n,值却不一样,谁也没有覆盖谁。它们放在哪?
回到上一页的顺序:最后进入的最先返回。后进先出,又是一个栈。
每调用一次Fact,计算机就往栈里放一条记录,记下这一次的n。返回的时候,这条记录出栈。
栈顶的那一条,就是正在算的那一次,下面的都在等。栈顶返回了,下面那条成了新的栈顶,拿着返回值接着算。
所以n=4放在Fact(4)自己的那条记录里。每一次调用都有自己的记录,4个n各住各的,互不干扰。
这个栈叫调用栈。不只是递归,程序里每调用一次函数,都会往调用栈里放一条记录:main调用Fact,也要放一条。递归只是同一个函数在里面放了好多条。
教材里的叫法
严蔚敏《数据结构》叫它"递归工作栈",每条记录叫"工作记录"。记录里除了参数,还有局部变量,以及返回后要接着执行哪一句。
调用栈的空间是有限的。
没有出口的递归,放到栈里看:每调用一次就入栈一条记录,只进不出,栈很快就满了。栈满了还要入栈,叫栈溢出,程序会崩溃。
c
int Bad(int n) {
return n * Bad(n - 1); /* 没有出口 */
}gcc编译时会警告infinite recursion detected,意思是发现了无穷递归。真去运行Bad(4),程序什么也没打印就崩溃了。在Windows上,退出码0xC00000FD就是栈溢出;在Linux上,一般会显示Segmentation fault。
有出口的递归,层数太多也会栈溢出。每一层都要占栈里的一条记录,这是递归比循环多付出的代价。
练习1:哪个能算出 4! ?
单选
int Fact(int n) { … }的函数体写成哪一个,Fact(4)能正确得出24?
A
if (n == 1) return 1; return n * Fact(n - 1);出口是1! = 1,每次规模减1,两个要点都有。
B
return n * Fact(n - 1);没有出口:会一直调用Fact(0)、Fact(-1)……停不下来。
C
if (n == 1) return 1; return n * Fact(n);规模没有变小:Fact(4)又调用Fact(4),一直在原地。
D
if (n == 0) return 0; return n * Fact(n - 1);出口给错了答案:一路乘到最后乘上0,结果是0。
递归要同时有两样:规模变小,和一个给对答案的出口。
练习2:跟着它走一遍
填空
c
int Sum(int n) {
if (n == 1) return 1;
return n + Sum(n - 1);
}执行Sum(4):
- 调用栈里最多同时有 条Sum的记录
Sum(2)返回- 最后的结果是
递:Sum(4)调用Sum(3),Sum(3)调用Sum(2),Sum(2)调用Sum(1),每调用一次入栈一条记录,到Sum(1)时栈里有4条。Sum(1)碰到出口,最先返回1,出栈。归:Sum(2)返回2 + 1 = 3,Sum(3)返回3 + 3 = 6,Sum(4)返回4 + 6 = 10,记录一条条出栈。
到这里你有了递归:一个问题用规模更小的同一个问题来解决,直到小到能直接给出答案。两个要点:规模变小、有出口。执行时先一层层往下调用(递),到了出口再带着结果一层层往回走(归)。最后进入的最先返回,所以计算机用调用栈管理这些调用:调用时入栈一条记录,返回时出栈;递归太深或没有出口,就会栈溢出。下一步栈到这里讲完了。下一节换一种结构:先来的先走,这就是队列。