文档介绍：第6章 递归算法
递归的概念
递归算法的执行过程
主
要 递归算法的设计方法
知 递归过程和运行时栈
识 递归算法的效率分析
点
递归算法到非递归算法的转换
设计举例
1
1 函数的递归调用
定义：函数直接或间接的调用自身叫函数的递归调用
int f(int x) int f1(int x) int f2(int t)
{ int y,z; { int y,z; { int a,c;
…… …… ……
z=f(y); z=f2(y); c=f1(a);
……. ……. …….
return(2*z); return(2*z); return(3+c);
} } }
f( )
f1( ) f2( )
调f
调f2 调f1
f( )
f1( ) f2( )
调
f 调f2 调f1
说明
1. 从图上可以看到，这两种递归调用都是无终止的自身调用
2. 显然，程序中不应出现这种无终止的递归调用，而只应出
现有限次数的、有终止的递归调用
3. 这可以用if语句来控制，只有在某一条件成立时才继续执行
递归调用，否则就不再继续。
例 有5个人坐在一起，问第5个人多少岁？他说比第4
个人大2岁。问第4个人岁数，他说比第3个人大2岁。
问第3个人，又说比第2个人大2岁。问第2个人，说比
第1个人大2岁。最后问第1个人，他说是10岁。请问第
5个人多大。
显然，这是一个递归问题。要求第5个人的年龄，就必
须先知道第4个人的年龄，而第4个人的年龄也不知道，
要求第4个人的年龄必须先知道第3个人的年龄，而第3
个人的年龄又取决于第2个人的年龄，第2个人的年龄取
决于第1个人的年龄。而且每一个人的年龄都比其前1个
人的年龄大2。
即 age（5）＝age（4）＋2
age（4）＝age（3）＋2
age（3）＝age（2）＋2
age（2）＝age（1）＋2
age（1）＝10
可以用式子表述如下：
age（n）＝10 （n＝1）
age（n）＝ age（n－1）＋2 （n＞1）
可以看到，当n＞1时，求第n个人的年龄的公式是
相同的。因此可以用一个函数表示上述关系。图表
示求第5个人年龄的过程。
，求解可分成两个阶段：
第一阶段是“回溯”，即将第n个人的年龄表示为第
（n－1）个人年龄的函数，而第（n－1）个人的年
龄仍然不知道，还要“回溯”到第（n－2）个人的
年龄……直到第1个人年龄。此时age（1）已知，不
必再向前推了。
第二阶段，采用递推方法，从第1个人的已知年龄推
算出第2个人的年龄（12岁），从第2个人的年龄推
算出第3个人的年龄（14岁）……一直推算出第5个
人的年龄（18岁）为止。
一个递归的问题可以分为“回溯”和“递推”两个
阶段。要经历许多步才能求出最后的值。
若要求递归过程不是无限制进行下去，必须具有一个结束递
归过程的条件。例如，age（1）＝10，就是使递归结束的条件
可以用一个函数来描述上述递归过程：
age（int n） /*求年龄的递归函数*/
{ int c； /* c用作存放函数的返回值的变量*/
if（n＝＝1）
c＝10；
else
c＝age（n－1）＋2；
return（c）；
｝
main（）