1
计算机程序设计基础
第六讲 递归
2
递归算法 在可计算性理论中占有重要地位，它是算法
设计的有力工具，对于拓展编程思路非常有用。就
递归算法而言并不涉及高深数学知识，只不过初学
者要建立起递归概念不十分容易。
我们先从一个最简单的例子导入。
递归及其实现
用递归算法求 n!
定义：函数 fact(n) = n!
fact(n-1) = (n-1)!
则有 fact(n) = n fact(n-1)
已知 fact(1) = 1
?
3
为了表述得直观清晰，我们定义两个结点,或结点 与
与结点。
图示的直观性与思维助力。
1、或结点
?,,B Z tr u eC Z fa ls eA ??? （真） （假）
A
条件 Z 条件 !Z
B C
A为“或结点,,A依不同条件会有两种不同的取值 B或
C。结点用 表示。
4
如果有多于 2种取值，可用下图,
Z 1 Z 2 … Z n
B C … G
A
条件为 Z1,Z2,…,Zn，取值为 B或 C,… 或 G
5
2、与结点
与结点要涂黑，相关联
的 B与 C之间要用弧线
连起来。
A为与结点,A的最终取值为 C结点的值，但为了
求得 C的值，得先求出 B结点的值,C是 B的函数。
A
B C
6
仍以求 n!为例画出如下与或图
A为或结点； B为直接可解结点，值为 1；
C为与结点，当 n>1时,A的取值即 C的值，而 C的值即
E的值，为了求得 E的值，需要先求出 D的值。 D值
fact(n-1)乘以 n即为 E的值。
A fact( n)
B
fact( 1)=1
C
n>1n=1
D
fact( n-1)
E
n* fact( n-1)
7
与结点可能有多个相关联的点，这时可描述为下图
A结点的值最终为 D的值，但为了求 D需先求 B和 C。从
图上看先求左边的点才能求最右边的点的值，我们
约定最右边 D点的值就是 A结点的值。
A
B DC
8
下面我们以 3！为例来画与或结点图，目的是体会递归
的含义。
C = 1
D = 2*C = 2
B = D = 2
E = 3*B = 3*2 = 6
A = E = 6
1=1
1
3>1
B
fact(2)
3*fact(2)
fact(3)
C
fact(1)
D
2* fact(1)
A
E
2>1
9
下面画出了调用和返回的递归示意图
B
fact(2)
=2*fact(1)
=2*1
=2 返回
D
A
fact(3)
=3*fact(2)
=3*2
=6
E 返回
C
fac t(1)
=1
调用
调用
10
从图可以想象,
欲求 fact(3)，先要求 fact(2)；要求 fact(2)先求 fact(1)。
就象剥一颗圆白菜，从外向里，一层层剥下来，到
了菜心，遇到 1的阶乘，其值为 1，到达了递归的边
界。然后再用 fact(n)=n*fact(n-1)这个普遍公式，从
里向外倒推回去得到 fact(n)的值。
为了把这个问题说得再透彻一点。我们画了如下的流
程图,
11
3 ＝＝ 1
f ac t ( 3)
真 假
调用
f ac t ( 2 )
计算
3 * f ac t ( 2 )
f ac t ( 2 ) f ac t ( 1 )
2 ＝＝ 1
真 假
调用
f ac t ( 1 )
计算
2 * f ac t ( 1 )
1 ＝＝ 1
真 假
f ac t ( 1 )
＝ 1
返回 返回
12
为了形象地描述递归过程，将上图改画成下图
f a c t ( 3 )
真 假
3 ==1
调用 f a c t ( 2 )
真 假
假 真
2 ==1
1 ==1
f a c t ( 2 ) =2 * f a c t ( 1 ) 返回
f a c t ( 3 ) =3 * f a c t ( 2 ) 返回
调用 f a c t ( 1 )
f ac t ( 1) =1
返回
13
在这个图中“内层”与“外层”有着相同的结构。它
们之间“你中有我，我中有你”，呈现相互依存的
关系。
为了进一步讲清递归的概念，将 递归 与 递推 做一比较。
仍以求阶乘为例。
递推 是从已知的初始条件出发，逐次去求所需要的阶
乘值。
如求 3！
初始条件 fact(1) = 1
fact(2) = 2*fact(1) = 2
fact(3) = 3*fact(2) = 6
14
这相当于从菜心“推到”外层。而 递归 算法的出发点
不放在初始条件上，而放在求解的目标上，从所求
的未知项出发逐次调用本身的求解过程，直到递归
的边界（即初始条件）。就本例而言，读者会认为
递归算法可能是多余的，费力而不讨好。 但许多实
际问题不可能或不容易找到显而易见的递推关系，
这时递归算法就表现出了明显的优越性。 下面我们
将会看到，递归算法比较符合人的思维方式，逻辑
性强，可将问题描述得简单扼要，具有良好的可读
性，易于理解，许多看来相当复杂，或难以下手的
问题，如果能够使用递归算法就会使问题变得易于
处理。下面举一个尽人皆知的例子 哈诺（ Hanoi）塔
问题。
15
故事：相传在古代印度的 Bramah庙中，有位僧子整天
把三根柱子上的金盘倒来倒去，原来他是想把 64个
一个比一个小的金盘从一根柱子上移到另一根柱子
上去。移动过程中恪守下述规则：每次只允许移动
一只盘，且大盘不得落在小盘上面。有人会觉得这
很简单，真的动手移盘就会发现，如以每秒移动一
只盘子的话，按照上述规则将 64只盘子从一个柱子
移至另一个柱子上，所需时间约为 5800亿年。
16
怎样编写这种程序？从思路上还是先从最简单的情况
分析起，搬一搬看，慢慢理出思路。
1、在 A柱上只有一只盘子，假定盘号为 1，这时只
需将该盘从 A搬至 C，一次完成，记为 move 1
from A to C
A B C
17
2、在 A柱上有二只盘子,1为小盘,2为大盘。
第（ 1）步将 1号盘从 A移至 B，这是为了让 2号盘能移动；
第（ 2）步将 2号盘从 A移至 C；
第（ 3）步再将 1号盘从 B移至 C；
这三步记为,
move 1 from A to B;
move 2 from A to C;
move 3 form B to C;
A B C
1
3
2
18
3、在 A柱上有 3只盘子，从小到大分别为 1号,2号,3号
第（ 1）步将 1号盘和 2号盘视为一个整体；先将二者作为
整体从 A移至 B，给 3号盘创造能够一次移至 C的机会。这
一步记为
move( 2,A,C,B)
意思是将上面的 2只盘子作为整体从 A借助 C移至 B。
第（ 2）步将 3号盘从 A移至 C，一次到位。记为
move 3 from A to C
第（ 3）步处于 B上的作为一个整体的 2只盘子，再移至 C。
这一步记为
move( 2,B,A,C)
意思是将 2只盘子作为整体从 B借助 A移至 C。
所谓 借助 是什么意思，等这件事做完了不言自明。
19
A B C
1 3
2
20
4、从题目的约束条件看，大盘上可以随便摞小盘，相
反则不允许。在将 1号和 2号盘当整体从 A移至 B的过
程中 move(2,A,C,B)实际上是分解为以下三步
第（ 1）,1步,move 1 form A to C;
第（ 1）,2步,move 2 form A to B;
第（ 1）,3步,move 1 form C to B;
经过以上步骤，将 1号和 2号盘作为整体从 A移至 B，为 3
号盘从 A移至 C创造了条件。同样,3号盘一旦到了 C，
就要考虑如何实现将 1号和 2号盘当整体从 B移至 C的
过程了。实际上 move(2,B,A,C)也要分解为三步,
第（ 3）,1步,move 1 form B to A;
第（ 3）,2步,move 2 form B to C;
第（ 3）,3步,move 1 form A to C;
21
5、看 move(2,A,C,B)是说要将 2只盼自从 A搬至 B，但
没有 C是不行的，因为第（ 1）,1步就要将 1盘从 A移
到 C，给 2盘创造条件从 A移至 B，然后再把 1盘从 C移
至 B。看到这里就能明白借助 C的含义了。因此，在
构思搬移过程的参量时，要把 3个柱子都用上。
6、定义搬移函数 move(n,A,B,C)，物理意义是将 n只
盘子从 A经 B搬到 C
输出
n:A to C
move( n-1,A,C,B ) move( n-1,B,A,C)
move( n,A,B,C )
考虑到前面已经
研究过的
(1)(2)(3)步，可
以将搬移过程
用如下的与或
结点图表示。
22
这里用与或结点的含义是分解为 (1)(2)(3)步。这 3步是
相关的，相互依存的，而且是有序的，从左至右执
行。
move(n,A,B,C) 分解为 3步
(1)move(n-1,A,C,B)理解为将上面的 n-1只盘子作为一
个整体从 A经 C移至 B；
(2)输出 n,A to C，理解将 n号盘从 A移至 C，是直接可
解结点；
(3)Move(n-1,B,A,C)理解为将上面的 n-1只盘子作为一
个整体从 B经 A移至 C。
23
这里显然是一种递归定义，当着解 move(n-1,A,C,B)时
又可想到，将其分解为 3步,
第 1步：将上面的 n-2只盘子作为一个整体从 A经 B到 C，
move(n-2,A,B,C)；
第 2步：第 n-1号盘子从 A直接移至 B，即 n-1:A to B；
第 3步：再将上面的 n-2只盘子作为一个整体从 C经 A移
至 B,move(n-2,C,A,B)；
下面，我们还是以 3只盘子为例画出递归的与或图。
24
这个图很象一颗倒置着的树，结点 move(3,A,B,C)是
树根，与结点是树的分枝，叶子都是直接可解结点。
输出
1:A to C
输出
3:A to C
move( 2,A,C,B )
move( 2,B,A,C )
move( 3,A,B,C )
输出
2:A to B
输出
1:C to B
输出
1:B to A
输出
2:B to C
输出
1:A to C
move (1,A,B,C ) m ove( 1,C,A,B) move (1,B,C,A ) m ove( 1,A,B,C)
25
m ov e ( 3,A,B,C )
m ov e ( 2,A,C,B )
输出 3,A t o C
m ov e ( 2,B,A,C )
m ov e ( 2,A,C,B ) 调用 m ov e ( 1,A,B,C )
m ov e ( 2,B,A,C ) 调用 m ov e ( 1,B,C,A )
返回
返回
调用
调用
返回
m ov e ( 1,A,B,C )
输出 2,A t o B
m ov e ( 1,C,A,B )
m ov e ( 1,B,C,A )
输出 2,B t o C
m ov e ( 1,A,B,C)
输出 1,A t o C
输出 1,B t o A
输出 1,C t o B
输出 1,A t o C
4
1
3
2
5
7
6
调用
调用
返回
返回
调用
m ov e ( 1,C,A,B )
m ov e ( 1,A,B,C )
26
输出 3,A to C
调用
m o v e (1,C,A,B )
输出,1,C to B
输出,2,A to B
m o v e (1,C,A,B )
调用
m o v e (1,A,B,C )
输出 1,A to C
m o v e (1,A,B,C )
m o v e (2,A,C,B )
调用
m o v e (2,A,C,B )
调用
m o v e (2,B,A,C )
调用
m o v e (1,A,B,C )
输出 1,A to C
输出,2,B to C
调用
m o v e (1,B,C,A )
输出 1,B to A
m o v e (1,B,C,A )
m o v e (2,B,A,C )
m o v e (1,A,B,C )
m o v e (3,A,B,C )
1
2
3
4
5
6
7
27
#include <stdio.h> //预编译命令
int step=1 ; //整型全局变量,预置 1,步数
void move(int,char,char,char); //声明要用到的被调用函数
void main() //主函数
{ //主程序开始
int n; //整型变量,n为盘数,
printf("请输入盘数 n=" ); //提示信息
scanf("%d",&n); //输入正整数 n
printf("在 3根柱子上移 %d只盘的步骤为,\n",n); //输出提示信息
move(n,'a','b','c'); //调用函数 move(n,'a','b','c')
} //主程序结束
//以下函数是被主程序调用的函数
void move(int m,char p,char q,char r) //自定义函数,m,p,q,r为形参,m 为整型变量
// p,q,r 为字符型变量
{ //自定义函数体开始
if (m==1) //如果 m为 1,则为直接可解结点,
{
printf("[%d] move 1# from %c to %c\n",step,p,r); //直接可解结点,输出移盘信息
step=step+1; //步数加 1
}
else //如果不为 1,则要调用 move(m-1)
{
move(m-1,p,r,q); //递归调用 move(m-1)
printf("[%d] move %d# from %c to %c\n",step,m,p,r); //直接可解结点,输出移盘信息
step=step+1; //步数加 1
move(m-1,q,p,r); //递归调用 move(m-1)
}
} //自定义函数体结束
28
?
1
11
1,
,1
2
5;
1
2
3
n
m
n n n
m m m
n m n
m m n
C m n
C C C
C
C
?
??
?
?
??
?
习题：
已知 表示从 个元素中取 个的组合数，又知
、试画出符合上述关系的与或结合图；
、指出哪个是直接可解结点；
、画出 求解结点图；
4,写出递归程序求解组合问题。
29
讨论问题 ——青蛙过河
该题是 2000年全国青少年信息学奥林匹克的一道试题。叙述如下,
一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱 L，
面积只容得下一只青蛙落脚，同样右岸也有一石柱 R，面积也只
容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们
将青蛙从小到大，用 1,2,…, n编号。规定初始时这队青蛙只
能趴在左岸的石头 L上，当然是一个落一个，小的落在大的上面。
不允许大的在小的上面。在小溪中有 S个石柱，有 y片荷叶，规定
溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，
大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多
只在其上。对于右岸的石柱 R，与左岸的石柱 L一样允许多个青
蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸
的 L上跳走后就不允许再跳回来；同样，从左岸 L上跳至右岸 R，
或从溪中荷叶或溪中石柱跳至右岸 R上的青蛙也不允许再离开。
问在已知溪中有 S根石柱和 y片荷叶的情况下，最多能跳过多少只
青蛙？
30
这题看起来较难，但是如果我们认真分析，理出思路，就可化
难为易。
思路,
1、简化问题，探索规律。先从个别再到一般，要善于对多个
因素作分解，孤立出一个一个因素来分析，化难为易。
2,定义函数
Jump(S,y) —— 最多可跳过河的青蛙数
其中,S —— 河中柱子数
y —— 荷叶数
31
3,先看简单情况，河中无柱子,S=0,
Jump(0,y)
当 y=1时,Jump(0,1)=2；
说明：河中有一片荷叶，可以过两只青蛙，起始时 L上有两
只青蛙,1#在 2#上面。
第一步,1# 跳到荷叶上；
第二步,2# 从 L直接跳至 R上；
第三步,1# 再从荷叶跳至 R上。
如下图,
2#
1#
2
1
3
L
左岸
R
右岸
32
当 y=2时,
Jump(0,2)=3；
说明：河中有两片荷叶时，可以过 3只青蛙。起始时,
1#,2#,3# 3只青蛙落在 L上,
第一步,1# 从 L跳至叶 1上,
第二步,2# 从 L跳至叶 2上,
第三步,3# 从 L直接跳至 R上,
第四步,2# 从叶 2跳至 R上,
第五步,1# 从叶 1跳至 R上,
叶1
3
1
5
L
R
叶2
2
4
采用归纳法,Jump(0,y)=y+1；
意思是：在河中没有石柱的情
况下，过河的青蛙数仅取决于荷
叶数，数目是荷叶数 +1。
33
再看 Jump(S,y)
先看一个最简单情况,S=1,y=1。
从图上看出需要 9步，跳过 4只青蛙。
1# 青蛙从 L － > Y；
2# 青蛙从 L － > S；
1# 青蛙从 Y － > S；
3# 青蛙从 L － > Y；
4# 青蛙从 L － > R；
3# 青蛙从 Y － > R；
1# 青蛙从 S － > Y；
2# 青蛙从 S － > R；
1# 青蛙从 Y － > R；
S
Y
5
4
6
L
R
1
2
3 7
8
91#
2#
4#
3#
3#
1#
2#
1#1#
34
t
L S Y R
L4 L3 L2 L1 S2 S1 R4 R3 R2 R1
0
1
2
3
4
5
6
7
8
9
4
4
4
4
4
3
3
3
3
2
2
1
2
2
2
2
2
1
1
1
1
1
3
1
1
4
4
4
4
4
3
3
3
3
2
2
1
表一
35
为了将过河过程描述得更清楚，我们给出了表 1。表中 L1 L2
L3 L4表示左岸石柱上落在一起的青蛙的高度位置。 L1 在
最上面,L4 在最下面的位置。引入这个信息就可比较容易
地看出对青蛙占位的约束条件。同理 R1 R2 R3 R4也是如
此。对水中石柱 S，也分成两个高度位置 S1 S2。对荷叶 Y无
须分层，因为它只允许一只青蛙落在其上。 t=0为初始时刻，
青蛙从小到大落在石柱 L上。 t=1为第一步,1#从 L跳至荷叶
Y上； L上只剩 2# 3# 4#。 T=2 为第二步； 2#从 L跳至石柱 S
上，处在 S2位置上,L上只剩 3#和 4#。 T=3为第三步,1#从
Y跳至 S，将 Y清空。这时你看,S上有 1#,2#,L上有 3#、
4#，好象是原来在 L上的 4只青蛙，分成了上下两部分，上
面的 2只通过荷叶 y转移到了 S上。这一过程是一分为二的过
程。即将 L上的一队青蛙，分解为两个队，每队各二只，且
将上面的二只转移到了 S上。这是我们可以考虑形成两个系
统，一个是 L,Y,R系统，一个是 S,Y,R系统。前者二只
青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。
从第五步到第九步可以看出的确是这么做的。
36
对于 LYR系统，相当于 Jump(0,1)
对于 SYR系统，相当于 Jump(0,1)
两个系统之和为 2*Jump(0,1)，
因此有,
Jump(1,1)=2*Jump(0,1)=2*2=4。
现在再看 S=2,y=1 Jump(2,1)
我们将河中的两个石柱称作 S1和 S2，
荷叶叫 y，考虑先将 L上的青蛙的一半
借助于 S2和 y转移到 S1上，当然是一
半小号的青蛙在 S1上，大的留在 L上。
y
L R
S1 S2
37
这样 L S1 S2 y R 系统分解为,
（ L S2 y R 系统） + （ S1 S2 y R 系统）
= 2 * （ L S2 y R 系统）
= 2 * Jump(1,1)
用归纳法
Jump(S,y)=2*Jump(S-1,y)
38
5,将上述分析出来的规律写成递归形式的与或结点图为,
Jum p(S,y)
y+1
S!=0S==0
Jum p(S-1,y) 2*Jump( S-1,y)
39
举例,S=3,y=4，算 Jump(3,4)
A=Jump(2,4)
2*B
2*10=20
Jump(3,4)
2*A
2*20=40
2*C
2*5=10
C=Jump(0,4)
S== 0
4+1 5
B=Jump(1,4)
3( 3,4 ) 2 ( 1 ) 2 (4 1 ) 4 0SJ u m p y? ? ? ? ?
40
#include <stdio.h> //预编译命令
int Jump(int,int); //声明有被调用函数
void main() //主函数
{ //主程序开始
int s,y,sum; //整型变量,s为河中石柱数,y为荷叶数
printf("请输入石柱数 s=" ); //提示信息
scanf("%d",&s); //输入正整数 s
printf("请输入荷叶数 y=" ); //提示信息
scanf("%d",&y); //输入正整数 y
sum=Jump(s,y); //Jump(s,y)为被调用函数
printf(“Jump(%d,%d)=%d \n",s,y,sum); //输出结果
} //主程序结束
//以下函数是被主程序调用的函数
int Jump(int r,int z) //整型自定义函数,r,z为形参
{ //自定义函数体开始
int k; //整型变量
if (r==0) //如果 r为 0,则为直接可解结点,
{
k=z+1; //直接可解结点,k值为 z+1
}
else //如果不为 1,则要调用 Jump(r-1,z)
{
k=2*Jump(r-1,z); //计算 Jump(r-1,z)再乘以 2赋给 k
}
return(k); //将 k的值返回给 Jump(s,y)
} //自定义函数体结束
41
结 束
计算机程序设计基础
第六讲 递归
2
递归算法 在可计算性理论中占有重要地位，它是算法
设计的有力工具，对于拓展编程思路非常有用。就
递归算法而言并不涉及高深数学知识，只不过初学
者要建立起递归概念不十分容易。
我们先从一个最简单的例子导入。
递归及其实现
用递归算法求 n!
定义：函数 fact(n) = n!
fact(n-1) = (n-1)!
则有 fact(n) = n fact(n-1)
已知 fact(1) = 1
?
3
为了表述得直观清晰，我们定义两个结点,或结点 与
与结点。
图示的直观性与思维助力。
1、或结点
?,,B Z tr u eC Z fa ls eA ??? （真） （假）
A
条件 Z 条件 !Z
B C
A为“或结点,,A依不同条件会有两种不同的取值 B或
C。结点用 表示。
4
如果有多于 2种取值，可用下图,
Z 1 Z 2 … Z n
B C … G
A
条件为 Z1,Z2,…,Zn，取值为 B或 C,… 或 G
5
2、与结点
与结点要涂黑，相关联
的 B与 C之间要用弧线
连起来。
A为与结点,A的最终取值为 C结点的值，但为了
求得 C的值，得先求出 B结点的值,C是 B的函数。
A
B C
6
仍以求 n!为例画出如下与或图
A为或结点； B为直接可解结点，值为 1；
C为与结点，当 n>1时,A的取值即 C的值，而 C的值即
E的值，为了求得 E的值，需要先求出 D的值。 D值
fact(n-1)乘以 n即为 E的值。
A fact( n)
B
fact( 1)=1
C
n>1n=1
D
fact( n-1)
E
n* fact( n-1)
7
与结点可能有多个相关联的点，这时可描述为下图
A结点的值最终为 D的值，但为了求 D需先求 B和 C。从
图上看先求左边的点才能求最右边的点的值，我们
约定最右边 D点的值就是 A结点的值。
A
B DC
8
下面我们以 3！为例来画与或结点图，目的是体会递归
的含义。
C = 1
D = 2*C = 2
B = D = 2
E = 3*B = 3*2 = 6
A = E = 6
1=1
1
3>1
B
fact(2)
3*fact(2)
fact(3)
C
fact(1)
D
2* fact(1)
A
E
2>1
9
下面画出了调用和返回的递归示意图
B
fact(2)
=2*fact(1)
=2*1
=2 返回
D
A
fact(3)
=3*fact(2)
=3*2
=6
E 返回
C
fac t(1)
=1
调用
调用
10
从图可以想象,
欲求 fact(3)，先要求 fact(2)；要求 fact(2)先求 fact(1)。
就象剥一颗圆白菜，从外向里，一层层剥下来，到
了菜心，遇到 1的阶乘，其值为 1，到达了递归的边
界。然后再用 fact(n)=n*fact(n-1)这个普遍公式，从
里向外倒推回去得到 fact(n)的值。
为了把这个问题说得再透彻一点。我们画了如下的流
程图,
11
3 ＝＝ 1
f ac t ( 3)
真 假
调用
f ac t ( 2 )
计算
3 * f ac t ( 2 )
f ac t ( 2 ) f ac t ( 1 )
2 ＝＝ 1
真 假
调用
f ac t ( 1 )
计算
2 * f ac t ( 1 )
1 ＝＝ 1
真 假
f ac t ( 1 )
＝ 1
返回 返回
12
为了形象地描述递归过程，将上图改画成下图
f a c t ( 3 )
真 假
3 ==1
调用 f a c t ( 2 )
真 假
假 真
2 ==1
1 ==1
f a c t ( 2 ) =2 * f a c t ( 1 ) 返回
f a c t ( 3 ) =3 * f a c t ( 2 ) 返回
调用 f a c t ( 1 )
f ac t ( 1) =1
返回
13
在这个图中“内层”与“外层”有着相同的结构。它
们之间“你中有我，我中有你”，呈现相互依存的
关系。
为了进一步讲清递归的概念，将 递归 与 递推 做一比较。
仍以求阶乘为例。
递推 是从已知的初始条件出发，逐次去求所需要的阶
乘值。
如求 3！
初始条件 fact(1) = 1
fact(2) = 2*fact(1) = 2
fact(3) = 3*fact(2) = 6
14
这相当于从菜心“推到”外层。而 递归 算法的出发点
不放在初始条件上，而放在求解的目标上，从所求
的未知项出发逐次调用本身的求解过程，直到递归
的边界（即初始条件）。就本例而言，读者会认为
递归算法可能是多余的，费力而不讨好。 但许多实
际问题不可能或不容易找到显而易见的递推关系，
这时递归算法就表现出了明显的优越性。 下面我们
将会看到，递归算法比较符合人的思维方式，逻辑
性强，可将问题描述得简单扼要，具有良好的可读
性，易于理解，许多看来相当复杂，或难以下手的
问题，如果能够使用递归算法就会使问题变得易于
处理。下面举一个尽人皆知的例子 哈诺（ Hanoi）塔
问题。
15
故事：相传在古代印度的 Bramah庙中，有位僧子整天
把三根柱子上的金盘倒来倒去，原来他是想把 64个
一个比一个小的金盘从一根柱子上移到另一根柱子
上去。移动过程中恪守下述规则：每次只允许移动
一只盘，且大盘不得落在小盘上面。有人会觉得这
很简单，真的动手移盘就会发现，如以每秒移动一
只盘子的话，按照上述规则将 64只盘子从一个柱子
移至另一个柱子上，所需时间约为 5800亿年。
16
怎样编写这种程序？从思路上还是先从最简单的情况
分析起，搬一搬看，慢慢理出思路。
1、在 A柱上只有一只盘子，假定盘号为 1，这时只
需将该盘从 A搬至 C，一次完成，记为 move 1
from A to C
A B C
17
2、在 A柱上有二只盘子,1为小盘,2为大盘。
第（ 1）步将 1号盘从 A移至 B，这是为了让 2号盘能移动；
第（ 2）步将 2号盘从 A移至 C；
第（ 3）步再将 1号盘从 B移至 C；
这三步记为,
move 1 from A to B;
move 2 from A to C;
move 3 form B to C;
A B C
1
3
2
18
3、在 A柱上有 3只盘子，从小到大分别为 1号,2号,3号
第（ 1）步将 1号盘和 2号盘视为一个整体；先将二者作为
整体从 A移至 B，给 3号盘创造能够一次移至 C的机会。这
一步记为
move( 2,A,C,B)
意思是将上面的 2只盘子作为整体从 A借助 C移至 B。
第（ 2）步将 3号盘从 A移至 C，一次到位。记为
move 3 from A to C
第（ 3）步处于 B上的作为一个整体的 2只盘子，再移至 C。
这一步记为
move( 2,B,A,C)
意思是将 2只盘子作为整体从 B借助 A移至 C。
所谓 借助 是什么意思，等这件事做完了不言自明。
19
A B C
1 3
2
20
4、从题目的约束条件看，大盘上可以随便摞小盘，相
反则不允许。在将 1号和 2号盘当整体从 A移至 B的过
程中 move(2,A,C,B)实际上是分解为以下三步
第（ 1）,1步,move 1 form A to C;
第（ 1）,2步,move 2 form A to B;
第（ 1）,3步,move 1 form C to B;
经过以上步骤，将 1号和 2号盘作为整体从 A移至 B，为 3
号盘从 A移至 C创造了条件。同样,3号盘一旦到了 C，
就要考虑如何实现将 1号和 2号盘当整体从 B移至 C的
过程了。实际上 move(2,B,A,C)也要分解为三步,
第（ 3）,1步,move 1 form B to A;
第（ 3）,2步,move 2 form B to C;
第（ 3）,3步,move 1 form A to C;
21
5、看 move(2,A,C,B)是说要将 2只盼自从 A搬至 B，但
没有 C是不行的，因为第（ 1）,1步就要将 1盘从 A移
到 C，给 2盘创造条件从 A移至 B，然后再把 1盘从 C移
至 B。看到这里就能明白借助 C的含义了。因此，在
构思搬移过程的参量时，要把 3个柱子都用上。
6、定义搬移函数 move(n,A,B,C)，物理意义是将 n只
盘子从 A经 B搬到 C
输出
n:A to C
move( n-1,A,C,B ) move( n-1,B,A,C)
move( n,A,B,C )
考虑到前面已经
研究过的
(1)(2)(3)步，可
以将搬移过程
用如下的与或
结点图表示。
22
这里用与或结点的含义是分解为 (1)(2)(3)步。这 3步是
相关的，相互依存的，而且是有序的，从左至右执
行。
move(n,A,B,C) 分解为 3步
(1)move(n-1,A,C,B)理解为将上面的 n-1只盘子作为一
个整体从 A经 C移至 B；
(2)输出 n,A to C，理解将 n号盘从 A移至 C，是直接可
解结点；
(3)Move(n-1,B,A,C)理解为将上面的 n-1只盘子作为一
个整体从 B经 A移至 C。
23
这里显然是一种递归定义，当着解 move(n-1,A,C,B)时
又可想到，将其分解为 3步,
第 1步：将上面的 n-2只盘子作为一个整体从 A经 B到 C，
move(n-2,A,B,C)；
第 2步：第 n-1号盘子从 A直接移至 B，即 n-1:A to B；
第 3步：再将上面的 n-2只盘子作为一个整体从 C经 A移
至 B,move(n-2,C,A,B)；
下面，我们还是以 3只盘子为例画出递归的与或图。
24
这个图很象一颗倒置着的树，结点 move(3,A,B,C)是
树根，与结点是树的分枝，叶子都是直接可解结点。
输出
1:A to C
输出
3:A to C
move( 2,A,C,B )
move( 2,B,A,C )
move( 3,A,B,C )
输出
2:A to B
输出
1:C to B
输出
1:B to A
输出
2:B to C
输出
1:A to C
move (1,A,B,C ) m ove( 1,C,A,B) move (1,B,C,A ) m ove( 1,A,B,C)
25
m ov e ( 3,A,B,C )
m ov e ( 2,A,C,B )
输出 3,A t o C
m ov e ( 2,B,A,C )
m ov e ( 2,A,C,B ) 调用 m ov e ( 1,A,B,C )
m ov e ( 2,B,A,C ) 调用 m ov e ( 1,B,C,A )
返回
返回
调用
调用
返回
m ov e ( 1,A,B,C )
输出 2,A t o B
m ov e ( 1,C,A,B )
m ov e ( 1,B,C,A )
输出 2,B t o C
m ov e ( 1,A,B,C)
输出 1,A t o C
输出 1,B t o A
输出 1,C t o B
输出 1,A t o C
4
1
3
2
5
7
6
调用
调用
返回
返回
调用
m ov e ( 1,C,A,B )
m ov e ( 1,A,B,C )
26
输出 3,A to C
调用
m o v e (1,C,A,B )
输出,1,C to B
输出,2,A to B
m o v e (1,C,A,B )
调用
m o v e (1,A,B,C )
输出 1,A to C
m o v e (1,A,B,C )
m o v e (2,A,C,B )
调用
m o v e (2,A,C,B )
调用
m o v e (2,B,A,C )
调用
m o v e (1,A,B,C )
输出 1,A to C
输出,2,B to C
调用
m o v e (1,B,C,A )
输出 1,B to A
m o v e (1,B,C,A )
m o v e (2,B,A,C )
m o v e (1,A,B,C )
m o v e (3,A,B,C )
1
2
3
4
5
6
7
27
#include <stdio.h> //预编译命令
int step=1 ; //整型全局变量,预置 1,步数
void move(int,char,char,char); //声明要用到的被调用函数
void main() //主函数
{ //主程序开始
int n; //整型变量,n为盘数,
printf("请输入盘数 n=" ); //提示信息
scanf("%d",&n); //输入正整数 n
printf("在 3根柱子上移 %d只盘的步骤为,\n",n); //输出提示信息
move(n,'a','b','c'); //调用函数 move(n,'a','b','c')
} //主程序结束
//以下函数是被主程序调用的函数
void move(int m,char p,char q,char r) //自定义函数,m,p,q,r为形参,m 为整型变量
// p,q,r 为字符型变量
{ //自定义函数体开始
if (m==1) //如果 m为 1,则为直接可解结点,
{
printf("[%d] move 1# from %c to %c\n",step,p,r); //直接可解结点,输出移盘信息
step=step+1; //步数加 1
}
else //如果不为 1,则要调用 move(m-1)
{
move(m-1,p,r,q); //递归调用 move(m-1)
printf("[%d] move %d# from %c to %c\n",step,m,p,r); //直接可解结点,输出移盘信息
step=step+1; //步数加 1
move(m-1,q,p,r); //递归调用 move(m-1)
}
} //自定义函数体结束
28
?
1
11
1,
,1
2
5;
1
2
3
n
m
n n n
m m m
n m n
m m n
C m n
C C C
C
C
?
??
?
?
??
?
习题：
已知 表示从 个元素中取 个的组合数，又知
、试画出符合上述关系的与或结合图；
、指出哪个是直接可解结点；
、画出 求解结点图；
4,写出递归程序求解组合问题。
29
讨论问题 ——青蛙过河
该题是 2000年全国青少年信息学奥林匹克的一道试题。叙述如下,
一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱 L，
面积只容得下一只青蛙落脚，同样右岸也有一石柱 R，面积也只
容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们
将青蛙从小到大，用 1,2,…, n编号。规定初始时这队青蛙只
能趴在左岸的石头 L上，当然是一个落一个，小的落在大的上面。
不允许大的在小的上面。在小溪中有 S个石柱，有 y片荷叶，规定
溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，
大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多
只在其上。对于右岸的石柱 R，与左岸的石柱 L一样允许多个青
蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸
的 L上跳走后就不允许再跳回来；同样，从左岸 L上跳至右岸 R，
或从溪中荷叶或溪中石柱跳至右岸 R上的青蛙也不允许再离开。
问在已知溪中有 S根石柱和 y片荷叶的情况下，最多能跳过多少只
青蛙？
30
这题看起来较难，但是如果我们认真分析，理出思路，就可化
难为易。
思路,
1、简化问题，探索规律。先从个别再到一般，要善于对多个
因素作分解，孤立出一个一个因素来分析，化难为易。
2,定义函数
Jump(S,y) —— 最多可跳过河的青蛙数
其中,S —— 河中柱子数
y —— 荷叶数
31
3,先看简单情况，河中无柱子,S=0,
Jump(0,y)
当 y=1时,Jump(0,1)=2；
说明：河中有一片荷叶，可以过两只青蛙，起始时 L上有两
只青蛙,1#在 2#上面。
第一步,1# 跳到荷叶上；
第二步,2# 从 L直接跳至 R上；
第三步,1# 再从荷叶跳至 R上。
如下图,
2#
1#
2
1
3
L
左岸
R
右岸
32
当 y=2时,
Jump(0,2)=3；
说明：河中有两片荷叶时，可以过 3只青蛙。起始时,
1#,2#,3# 3只青蛙落在 L上,
第一步,1# 从 L跳至叶 1上,
第二步,2# 从 L跳至叶 2上,
第三步,3# 从 L直接跳至 R上,
第四步,2# 从叶 2跳至 R上,
第五步,1# 从叶 1跳至 R上,
叶1
3
1
5
L
R
叶2
2
4
采用归纳法,Jump(0,y)=y+1；
意思是：在河中没有石柱的情
况下，过河的青蛙数仅取决于荷
叶数，数目是荷叶数 +1。
33
再看 Jump(S,y)
先看一个最简单情况,S=1,y=1。
从图上看出需要 9步，跳过 4只青蛙。
1# 青蛙从 L － > Y；
2# 青蛙从 L － > S；
1# 青蛙从 Y － > S；
3# 青蛙从 L － > Y；
4# 青蛙从 L － > R；
3# 青蛙从 Y － > R；
1# 青蛙从 S － > Y；
2# 青蛙从 S － > R；
1# 青蛙从 Y － > R；
S
Y
5
4
6
L
R
1
2
3 7
8
91#
2#
4#
3#
3#
1#
2#
1#1#
34
t
L S Y R
L4 L3 L2 L1 S2 S1 R4 R3 R2 R1
0
1
2
3
4
5
6
7
8
9
4
4
4
4
4
3
3
3
3
2
2
1
2
2
2
2
2
1
1
1
1
1
3
1
1
4
4
4
4
4
3
3
3
3
2
2
1
表一
35
为了将过河过程描述得更清楚，我们给出了表 1。表中 L1 L2
L3 L4表示左岸石柱上落在一起的青蛙的高度位置。 L1 在
最上面,L4 在最下面的位置。引入这个信息就可比较容易
地看出对青蛙占位的约束条件。同理 R1 R2 R3 R4也是如
此。对水中石柱 S，也分成两个高度位置 S1 S2。对荷叶 Y无
须分层，因为它只允许一只青蛙落在其上。 t=0为初始时刻，
青蛙从小到大落在石柱 L上。 t=1为第一步,1#从 L跳至荷叶
Y上； L上只剩 2# 3# 4#。 T=2 为第二步； 2#从 L跳至石柱 S
上，处在 S2位置上,L上只剩 3#和 4#。 T=3为第三步,1#从
Y跳至 S，将 Y清空。这时你看,S上有 1#,2#,L上有 3#、
4#，好象是原来在 L上的 4只青蛙，分成了上下两部分，上
面的 2只通过荷叶 y转移到了 S上。这一过程是一分为二的过
程。即将 L上的一队青蛙，分解为两个队，每队各二只，且
将上面的二只转移到了 S上。这是我们可以考虑形成两个系
统，一个是 L,Y,R系统，一个是 S,Y,R系统。前者二只
青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。
从第五步到第九步可以看出的确是这么做的。
36
对于 LYR系统，相当于 Jump(0,1)
对于 SYR系统，相当于 Jump(0,1)
两个系统之和为 2*Jump(0,1)，
因此有,
Jump(1,1)=2*Jump(0,1)=2*2=4。
现在再看 S=2,y=1 Jump(2,1)
我们将河中的两个石柱称作 S1和 S2，
荷叶叫 y，考虑先将 L上的青蛙的一半
借助于 S2和 y转移到 S1上，当然是一
半小号的青蛙在 S1上，大的留在 L上。
y
L R
S1 S2
37
这样 L S1 S2 y R 系统分解为,
（ L S2 y R 系统） + （ S1 S2 y R 系统）
= 2 * （ L S2 y R 系统）
= 2 * Jump(1,1)
用归纳法
Jump(S,y)=2*Jump(S-1,y)
38
5,将上述分析出来的规律写成递归形式的与或结点图为,
Jum p(S,y)
y+1
S!=0S==0
Jum p(S-1,y) 2*Jump( S-1,y)
39
举例,S=3,y=4，算 Jump(3,4)
A=Jump(2,4)
2*B
2*10=20
Jump(3,4)
2*A
2*20=40
2*C
2*5=10
C=Jump(0,4)
S== 0
4+1 5
B=Jump(1,4)
3( 3,4 ) 2 ( 1 ) 2 (4 1 ) 4 0SJ u m p y? ? ? ? ?
40
#include <stdio.h> //预编译命令
int Jump(int,int); //声明有被调用函数
void main() //主函数
{ //主程序开始
int s,y,sum; //整型变量,s为河中石柱数,y为荷叶数
printf("请输入石柱数 s=" ); //提示信息
scanf("%d",&s); //输入正整数 s
printf("请输入荷叶数 y=" ); //提示信息
scanf("%d",&y); //输入正整数 y
sum=Jump(s,y); //Jump(s,y)为被调用函数
printf(“Jump(%d,%d)=%d \n",s,y,sum); //输出结果
} //主程序结束
//以下函数是被主程序调用的函数
int Jump(int r,int z) //整型自定义函数,r,z为形参
{ //自定义函数体开始
int k; //整型变量
if (r==0) //如果 r为 0,则为直接可解结点,
{
k=z+1; //直接可解结点,k值为 z+1
}
else //如果不为 1,则要调用 Jump(r-1,z)
{
k=2*Jump(r-1,z); //计算 Jump(r-1,z)再乘以 2赋给 k
}
return(k); //将 k的值返回给 Jump(s,y)
} //自定义函数体结束
41
结 束
