1
计算机程序设计基础
第五讲 函数
2
三、数组
问题：编程求解
1
n k
x
x
?
?
现假定 n=6,k=4
我们用函数来编写这个题的程序，参考程序如下,
#include <stdio.h> //预编译命令
#define n 6 //定义 n为 6
#define k 4 //定义 k为 4
void main() //主函数
{ //主程序开始
printf("sum of %dth powers of integers from 1 to %d=",k,n );
//提示信息
printf("%d\n",SOP(n,k)); //输出结果,其中
//SOP(n,k)为被调用函数
} //主程序结束
3
//以下函数是被主程序调用的函数
int SOP(m,l) //整型自定义函数,m,l 为形参
int m,l; //形参 m,l 为整型变量
{ //自定义函数体开始
int i,sum; //整型变量 i,sum
sum=0; //初始化累加器
for (i=1; i<=m; i=i+1 ) //计数循环 (i)
{ //循环体开始
sum=sum+power( i,l ); //累加
} //循环体开始
return (sum) ; //返回值 sum给函数 sop(n,k)
} //自定义函数体结束
//以下函数是被函数 sop(n,k)调用的函数
int power(p,q) //整型自定义函数
int p,q; //形参 p,q 为整型变量
{ //自定义函数体开始
int i,product; //整型变量
product=1; //初始化累乘器
for(i=1; i<=q; i=i+1) //计数循环 ( i )
{ //循环体开始 ( i )
product=product*p; //累乘
} //循环体结束 ( i )
return(product); //累乘值 product返回给 power
} //自定义函数体结束
4
自定义函数
<数据类型 > <函数名 > (<参数表 >)
例, int power(p,n)
power为函数名，要以英文字母开头。
int是函数值的数据类型，这里是 int（整型）。
(p,n)括号中的 p,n为函数的形式参数，形式参数也要定义其数据
类型。
函数定义的一般格式,
<数据类型 > <函数名 > (<参数表 >)
<参数说明 ;>
{
<说明语句 >
<执行语句 >
}
为了突出重点，先学会基本东西，省略掉一些事情先不讲。
5
1、形式参数是在定义函数时放在函数名后括号中的参数。在未进
行函数调用时，并不对形式参数分配内存单元。在发生函数调
用时，立刻给形式参数分配内存单元。调用结束后，释放掉行
参所占的内存单元。
2、因此，形参变量属于局部变量，其作用域在它所在的函数体内。
3、在定义函数的时候，必须指定形参变量的类型，如何指定？有
二种方法,
形式参数与实在参数
(1) int power(p,n)
int p,n;
{
……
}
(2) int power(int p,int n)
{
……
}
有些编译系统不认识第（ 2）种形式
6
4、实在参数是一个具有确定值的表达式。函数在调用时，将实在
参数赋给形式参数。
比如，主函数调用 SOP(n,k)，这时,n,k为是在参数,n的
值为 6,k的值为 4。在被调用函数定义中,int SOP(m,l)中的 m,l
为形式参数，在 SOP被调用时，系统给 m,l这两个形式参数分配
了内存单元。之后,n的值 6赋给 m,k的值 4赋给 l。
m l
4 6
实在参数的个数及类型应与形式参数一致。赋值时前后对应关系
不会改变。下面画出主函数与 SOP函数，调用与被调用时参数
传递关系,
7
主函数执行下述语句时,
printf(“%d \n”,SOP(n,k));
传值给被调用函数
int SOP(m,l)
n的值 6传给 m,
k的值 4传给 l。
6和 4为实在参数,m和 l为形式参数。
被调用函数在其形式参数被赋值之后，开始执行函数体，先是让
累加器初始化为 0（ sum=0），接着进入以 i为控制变量的计算
循环,i从 1变到 m（ m=6），即累加 m次（即 6次）。循环体为
sum=sum+power(i,l)。当 6次循环执行完后，实现的是
6
1
( 4 )l
x
s u m x l
?
???
注意这里 是由另一个自定义函数 power(i,l)实现的。 li
8
power(i,l)处在 SOP(m,l)函数中，表示 SOP函数去调用
power 函数。其中 i,l为实在参数，而 int power(p,q)中
的 p,q为形式参数。
比如，执行 SOP(6,4)时,l=4,m=6,
当 i=1时,
sum=sum+power(1,4)
这里 1,4为实在参数，调用 power(p,q)，两个形式参数
p,q分别被赋以 1,4。
9
执行 S O P ( 6,4) l = 4
s u m = 0
i = 1,s u m = s u m + p o w e r ( i,l )
= 0 + 1
= 1
i = 2,s u m = s u m + p o w e r ( i,l )
= 1 + 16
= 17
i = 3,s u m = s u m + p o w e r ( i,l )
= 17 + 81
= 98
i = 4,s u m = s u m + p o w e r ( i,l )
= 98 + 256
= 354
i = 5,s u m = s u m + p o w e r ( i,l )
= 354 + 625
= 979
i = 6,s u m = s u m + p o w e r ( i,l )
= 979 + 1296
= 2275
r e t u r n ( s u m )
2275
返回
执行 p o w e r ( 1,4),
p r od u c t = 1*1*1*1
r e t u r n ( 1) = 1
调用
返回
执行 p o w e r ( 2,4),
p r od u c t = 2*2*2*2
r e t u r n ( 16) = 16
调用
返回
执行 p o w e r ( 3,4),
p r od u c t = 3*3*3*3
r e t u r n ( 81) = 81
调用
返回
执行 p o w e r ( 4,4),
p r od u c t = 4*4*4*4
r e t u r n ( 256) = 256
调用
返回
执行 p o w e r ( 5,4),
p r od u c t = 5*5*5*5
r e t u r n ( 625) = 625
调用
返回
执行 p o w e r ( 6,4),
p r od u c t = 6*6*6* 6
r e t u r n ( 1296) = 1296
调用
返回
S O P ( n,k )
调用
10
递归算法 在可计算性理论中占有重要地位，它是算法
设计的有力工具，对于拓展编程思路非常有用。就
递归算法而言并不涉及高深数学知识，只不过初学
者要建立起递归概念不十分容易。
我们先从一个最简单的例子导入。
递归及其实现
用递归算法求 n!
定义：函数 fact(n) = n!
fact(n-1) = (n-1)!
则有 fact(n) = n fact(n-1)
已知 fact(1) = 1
?
11
为了表述得直观清晰，我们定义两个结点,或结点 与
与结点。
图示的直观性与思维助力。
1、或结点
?,,B Z tr u eC Z fa ls eA ??? （真） （假）
A
条件 Z 条件 !Z
B C
A为“或结点,,A依不同条件会有两种不同的取值 B或
C。结点用 表示。
12
如果有多于 2种取值，可用下图,
Z 1 Z 2 … Z n
B C … G
A
条件为 Z1,Z2,…,Zn，取值为 B或 C,… 或 G
13
2、与结点
与结点要涂黑，相关联
的 B与 C之间要用弧线
连起来。
A为与结点,A的最终取值为 C结点的值，但为了
求得 C的值，得先求出 B结点的值,C是 B的函数。
A
B C
14
仍以求 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)
15
与结点可能有多个相关联的点，这时可描述为下图
A结点的值最终为 D的值，但为了求 D需先求 B和 C。从
图上看先求左边的点才能求最右边的点的值，我们
约定最右边 D点的值就是 A结点的值。
A
B DC
16
下面我们以 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
17
下面画出了调用和返回的递归示意图
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
调用
调用
18
从图可以想象,
欲求 fact(3)，先要求 fact(2)；要求 fact(2)先求 fact(1)。
就象剥一颗圆白菜，从外向里，一层层剥下来，到
了菜心，遇到 1的阶乘，其值为 1，到达了递归的边
界。然后再用 fact(n)=n*fact(n-1)这个普遍公式，从
里向外倒推回去得到 fact(n)的值。
为了把这个问题说得再透彻一点。我们画了如下的流
程图,
19
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
返回 返回
20
为了形象地描述递归过程，将上图改画成下图
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
返回
21
在这个图中“内层”与“外层”有着相同的结构。它
们之间“你中有我，我中有你”，呈现相互依存的
关系。
为了进一步讲清递归的概念，将 递归 与 递推 做一比较。
仍以求阶乘为例。
递推 是从已知的初始条件出发，逐次去求所需要的阶
乘值。
如求 3！
初始条件 fact(1) = 1
fact(2) = 2*fact(1) = 2
fact(3) = 3*fact(2) = 6
22
这相当于从菜心“推到”外层。而 递归 算法的出发点
不放在初始条件上，而放在求解的目标上，从所求
的未知项出发逐次调用本身的求解过程，直到递归
的边界（即初始条件）。就本例而言，读者会认为
递归算法可能是多余的，费力而不讨好。 但许多实
际问题不可能或不容易找到显而易见的递推关系，
这时递归算法就表现出了明显的优越性。 下面我们
将会看到，递归算法比较符合人的思维方式，逻辑
性强，可将问题描述得简单扼要，具有良好的可读
性，易于理解，许多看来相当复杂，或难以下手的
问题，如果能够使用递归算法就会使问题变得易于
处理。下面举一个尽人皆知的例子 哈诺（ Hanoi）塔
问题。
23
故事：相传在古代印度的 Bramah庙中，有位僧子整天
把三根柱子上的金盘倒来倒去，原来他是想把 64个
一个比一个小的金盘从一根柱子上移到另一根柱子
上去。移动过程中恪守下述规则：每次只允许移动
一只盘，且大盘不得落在小盘上面。有人会觉得这
很简单，真的动手移盘就会发现，如以每秒移动一
只盘子的话，按照上述规则将 64只盘子从一个柱子
移至另一个柱子上，所需时间约为 5800亿年。
24
怎样编写这种程序？从思路上还是先从最简单的情况
分析起，搬一搬看，慢慢理出思路。
1、在 A柱上只有一只盘子，假定盘号为 1，这时只
需将该盘从 A搬至 C，一次完成，记为 move 1
from A to C
A B C
25
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
26
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。
所谓 借助 是什么意思，等这件事做完了不言自明。
27
A B C
1 3
2
28
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;
29
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)步，可
以将搬移过程
用如下的与或
结点图表示。
30
这里用与或结点的含义是分解为 (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。
31
这里显然是一种递归定义，当着解 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只盘子为例画出递归的与或图。
32
这个图很象一颗倒置着的树，结点 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)
33
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 )
34
输出 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
35
#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)
}
} //自定义函数体结束
36
?
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,写出递归程序求解组合问题。
计算机程序设计基础
第五讲 函数
2
三、数组
问题：编程求解
1
n k
x
x
?
?
现假定 n=6,k=4
我们用函数来编写这个题的程序，参考程序如下,
#include <stdio.h> //预编译命令
#define n 6 //定义 n为 6
#define k 4 //定义 k为 4
void main() //主函数
{ //主程序开始
printf("sum of %dth powers of integers from 1 to %d=",k,n );
//提示信息
printf("%d\n",SOP(n,k)); //输出结果,其中
//SOP(n,k)为被调用函数
} //主程序结束
3
//以下函数是被主程序调用的函数
int SOP(m,l) //整型自定义函数,m,l 为形参
int m,l; //形参 m,l 为整型变量
{ //自定义函数体开始
int i,sum; //整型变量 i,sum
sum=0; //初始化累加器
for (i=1; i<=m; i=i+1 ) //计数循环 (i)
{ //循环体开始
sum=sum+power( i,l ); //累加
} //循环体开始
return (sum) ; //返回值 sum给函数 sop(n,k)
} //自定义函数体结束
//以下函数是被函数 sop(n,k)调用的函数
int power(p,q) //整型自定义函数
int p,q; //形参 p,q 为整型变量
{ //自定义函数体开始
int i,product; //整型变量
product=1; //初始化累乘器
for(i=1; i<=q; i=i+1) //计数循环 ( i )
{ //循环体开始 ( i )
product=product*p; //累乘
} //循环体结束 ( i )
return(product); //累乘值 product返回给 power
} //自定义函数体结束
4
自定义函数
<数据类型 > <函数名 > (<参数表 >)
例, int power(p,n)
power为函数名，要以英文字母开头。
int是函数值的数据类型，这里是 int（整型）。
(p,n)括号中的 p,n为函数的形式参数，形式参数也要定义其数据
类型。
函数定义的一般格式,
<数据类型 > <函数名 > (<参数表 >)
<参数说明 ;>
{
<说明语句 >
<执行语句 >
}
为了突出重点，先学会基本东西，省略掉一些事情先不讲。
5
1、形式参数是在定义函数时放在函数名后括号中的参数。在未进
行函数调用时，并不对形式参数分配内存单元。在发生函数调
用时，立刻给形式参数分配内存单元。调用结束后，释放掉行
参所占的内存单元。
2、因此，形参变量属于局部变量，其作用域在它所在的函数体内。
3、在定义函数的时候，必须指定形参变量的类型，如何指定？有
二种方法,
形式参数与实在参数
(1) int power(p,n)
int p,n;
{
……
}
(2) int power(int p,int n)
{
……
}
有些编译系统不认识第（ 2）种形式
6
4、实在参数是一个具有确定值的表达式。函数在调用时，将实在
参数赋给形式参数。
比如，主函数调用 SOP(n,k)，这时,n,k为是在参数,n的
值为 6,k的值为 4。在被调用函数定义中,int SOP(m,l)中的 m,l
为形式参数，在 SOP被调用时，系统给 m,l这两个形式参数分配
了内存单元。之后,n的值 6赋给 m,k的值 4赋给 l。
m l
4 6
实在参数的个数及类型应与形式参数一致。赋值时前后对应关系
不会改变。下面画出主函数与 SOP函数，调用与被调用时参数
传递关系,
7
主函数执行下述语句时,
printf(“%d \n”,SOP(n,k));
传值给被调用函数
int SOP(m,l)
n的值 6传给 m,
k的值 4传给 l。
6和 4为实在参数,m和 l为形式参数。
被调用函数在其形式参数被赋值之后，开始执行函数体，先是让
累加器初始化为 0（ sum=0），接着进入以 i为控制变量的计算
循环,i从 1变到 m（ m=6），即累加 m次（即 6次）。循环体为
sum=sum+power(i,l)。当 6次循环执行完后，实现的是
6
1
( 4 )l
x
s u m x l
?
???
注意这里 是由另一个自定义函数 power(i,l)实现的。 li
8
power(i,l)处在 SOP(m,l)函数中，表示 SOP函数去调用
power 函数。其中 i,l为实在参数，而 int power(p,q)中
的 p,q为形式参数。
比如，执行 SOP(6,4)时,l=4,m=6,
当 i=1时,
sum=sum+power(1,4)
这里 1,4为实在参数，调用 power(p,q)，两个形式参数
p,q分别被赋以 1,4。
9
执行 S O P ( 6,4) l = 4
s u m = 0
i = 1,s u m = s u m + p o w e r ( i,l )
= 0 + 1
= 1
i = 2,s u m = s u m + p o w e r ( i,l )
= 1 + 16
= 17
i = 3,s u m = s u m + p o w e r ( i,l )
= 17 + 81
= 98
i = 4,s u m = s u m + p o w e r ( i,l )
= 98 + 256
= 354
i = 5,s u m = s u m + p o w e r ( i,l )
= 354 + 625
= 979
i = 6,s u m = s u m + p o w e r ( i,l )
= 979 + 1296
= 2275
r e t u r n ( s u m )
2275
返回
执行 p o w e r ( 1,4),
p r od u c t = 1*1*1*1
r e t u r n ( 1) = 1
调用
返回
执行 p o w e r ( 2,4),
p r od u c t = 2*2*2*2
r e t u r n ( 16) = 16
调用
返回
执行 p o w e r ( 3,4),
p r od u c t = 3*3*3*3
r e t u r n ( 81) = 81
调用
返回
执行 p o w e r ( 4,4),
p r od u c t = 4*4*4*4
r e t u r n ( 256) = 256
调用
返回
执行 p o w e r ( 5,4),
p r od u c t = 5*5*5*5
r e t u r n ( 625) = 625
调用
返回
执行 p o w e r ( 6,4),
p r od u c t = 6*6*6* 6
r e t u r n ( 1296) = 1296
调用
返回
S O P ( n,k )
调用
10
递归算法 在可计算性理论中占有重要地位，它是算法
设计的有力工具，对于拓展编程思路非常有用。就
递归算法而言并不涉及高深数学知识，只不过初学
者要建立起递归概念不十分容易。
我们先从一个最简单的例子导入。
递归及其实现
用递归算法求 n!
定义：函数 fact(n) = n!
fact(n-1) = (n-1)!
则有 fact(n) = n fact(n-1)
已知 fact(1) = 1
?
11
为了表述得直观清晰，我们定义两个结点,或结点 与
与结点。
图示的直观性与思维助力。
1、或结点
?,,B Z tr u eC Z fa ls eA ??? （真） （假）
A
条件 Z 条件 !Z
B C
A为“或结点,,A依不同条件会有两种不同的取值 B或
C。结点用 表示。
12
如果有多于 2种取值，可用下图,
Z 1 Z 2 … Z n
B C … G
A
条件为 Z1,Z2,…,Zn，取值为 B或 C,… 或 G
13
2、与结点
与结点要涂黑，相关联
的 B与 C之间要用弧线
连起来。
A为与结点,A的最终取值为 C结点的值，但为了
求得 C的值，得先求出 B结点的值,C是 B的函数。
A
B C
14
仍以求 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)
15
与结点可能有多个相关联的点，这时可描述为下图
A结点的值最终为 D的值，但为了求 D需先求 B和 C。从
图上看先求左边的点才能求最右边的点的值，我们
约定最右边 D点的值就是 A结点的值。
A
B DC
16
下面我们以 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
17
下面画出了调用和返回的递归示意图
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
调用
调用
18
从图可以想象,
欲求 fact(3)，先要求 fact(2)；要求 fact(2)先求 fact(1)。
就象剥一颗圆白菜，从外向里，一层层剥下来，到
了菜心，遇到 1的阶乘，其值为 1，到达了递归的边
界。然后再用 fact(n)=n*fact(n-1)这个普遍公式，从
里向外倒推回去得到 fact(n)的值。
为了把这个问题说得再透彻一点。我们画了如下的流
程图,
19
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
返回 返回
20
为了形象地描述递归过程，将上图改画成下图
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
返回
21
在这个图中“内层”与“外层”有着相同的结构。它
们之间“你中有我，我中有你”，呈现相互依存的
关系。
为了进一步讲清递归的概念，将 递归 与 递推 做一比较。
仍以求阶乘为例。
递推 是从已知的初始条件出发，逐次去求所需要的阶
乘值。
如求 3！
初始条件 fact(1) = 1
fact(2) = 2*fact(1) = 2
fact(3) = 3*fact(2) = 6
22
这相当于从菜心“推到”外层。而 递归 算法的出发点
不放在初始条件上，而放在求解的目标上，从所求
的未知项出发逐次调用本身的求解过程，直到递归
的边界（即初始条件）。就本例而言，读者会认为
递归算法可能是多余的，费力而不讨好。 但许多实
际问题不可能或不容易找到显而易见的递推关系，
这时递归算法就表现出了明显的优越性。 下面我们
将会看到，递归算法比较符合人的思维方式，逻辑
性强，可将问题描述得简单扼要，具有良好的可读
性，易于理解，许多看来相当复杂，或难以下手的
问题，如果能够使用递归算法就会使问题变得易于
处理。下面举一个尽人皆知的例子 哈诺（ Hanoi）塔
问题。
23
故事：相传在古代印度的 Bramah庙中，有位僧子整天
把三根柱子上的金盘倒来倒去，原来他是想把 64个
一个比一个小的金盘从一根柱子上移到另一根柱子
上去。移动过程中恪守下述规则：每次只允许移动
一只盘，且大盘不得落在小盘上面。有人会觉得这
很简单，真的动手移盘就会发现，如以每秒移动一
只盘子的话，按照上述规则将 64只盘子从一个柱子
移至另一个柱子上，所需时间约为 5800亿年。
24
怎样编写这种程序？从思路上还是先从最简单的情况
分析起，搬一搬看，慢慢理出思路。
1、在 A柱上只有一只盘子，假定盘号为 1，这时只
需将该盘从 A搬至 C，一次完成，记为 move 1
from A to C
A B C
25
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
26
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。
所谓 借助 是什么意思，等这件事做完了不言自明。
27
A B C
1 3
2
28
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;
29
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)步，可
以将搬移过程
用如下的与或
结点图表示。
30
这里用与或结点的含义是分解为 (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。
31
这里显然是一种递归定义，当着解 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只盘子为例画出递归的与或图。
32
这个图很象一颗倒置着的树，结点 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)
33
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 )
34
输出 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
35
#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)
}
} //自定义函数体结束
36
?
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,写出递归程序求解组合问题。
