2
存在算法调用自己的情况：
若一个算法直接的或间接的 调用自己本身,则称这
个算法是递归算法。
（ 1） 问题的定义是递推的
阶乘函数的 常见定义 是：
6.1递归的概念
3
也可定义为：
写成函数形式，则为：
这种函数定义的方法是 用阶乘函数
自己本身定义了阶乘函数,称公式（ 6
– 3）是阶乘函数的 递推定义式 。
4
（ 2）问题的解法存在自调用
一个典型的例子是在 有序数组中 查找一个数
据元素是否存在的 折半查找算法 。
5
6.2递归算法的执行过程
例 6-1 给出按照公式 6-3计算阶乘函数的递归算法,
并给出 n = 3时递归算法的执行过程 。
设计：按照公式 6-3计算阶乘函数的递归算法如下：
long int Fact(int n)
{ int x;
long int y;
if(n < 0) /*(n < 0时阶乘无定义 */
{ printf(,参数错 ！, );
return -1; }
if(n == 0) return 1;
else {y = Fact(n - 1); /*递归调用 */
return n * y; }
}
6
为说明该递归算法的执行过程，设计主函数如下
void main(void)
{
long int fn;
fn = Fact(3);
}
主函数用 实参 n = 3调用了递归算法 Fact(3)，而 Fact(3)要通
过 调用 Fact(2),Fact(2)要通过 调用 Fact(1),Fact(1)要通过
调用 Fact(0)来得出计算结果。 Fact(3)的递归调用过程如图 6-2
所示，其中,实线箭头表示函数调用，虚线箭头表示函数返回,
此函数在返回时函数名将带回返回值 。
7
例 6-2 给出在 有序数组 a中查找数据元素 x是否存在 的递归算法，
并给出如图 6-1所示实际数据的递归算法的执行过程。
设计,算法的参数包括,有序数组 a，要查找的数据元素 x，
数组下界下标 low，数组上界下标 high。当在数组 a中查找到数据
元素 x时函数返回数组 a的下标 ；当在数组 a中查找不到数据元素 x
时函数返回 -1。
8
递归 算法如下：
int BSearch(int a[],int x,int low,int high)
{ int mid;
if(low > high) return -1; /*查找不成功 */
mid = (low + high) / 2;
if(x == a[mid]) return mid; /*查找成功 */
else if(x < a[mid])
return BSearch(a,x,low,mid-1); /*在下半区查找 */
else
return BSearch(a,x,mid+1,high); /*在上半区查找 */
}
9
测试主函数设计如下：
# include <stdio.h>
main(void)
{ int a[] = {1,3,4,5,17,18,31,33};
int x = 17;
int bn;
bn = BSearch(a,x,0,7);
if(bn == -1) printf("x不在数组 a中 ");
else printf("x在数组 a的下标 %d中 ",bn);
}
10
BSearch(a,x,0,7)的递归调用过程如图 6-3所示，
其中,实箭头 表示函数 调用, 虚箭头 表示函数的 返回值 。
11
6.3递归算法的设计方法
递归算法既是一种有效的 算法设计 方法, 也是一种有效的 分析问题 的方
法 。 递归算法求解问题的 基本思想 是：对于一个较为复杂的问题, 把原问题
分解成若干个相对简单且类同的子问题, 这样较为复杂的原问题就变成了相
对简单的子问题；而简单到一定程度的子问题可以直接求解；这样, 原问题
就可递推得到解 。
并不是每个问题都适宜于用递归算法求解 。 适宜于用递归算法求解的问
题的 充分必要条件 是：
（ 1） 问题具有某种可借用的类同自身的子问题描述的性质；
（ 2） 某一有限步的子问题 （ 也称作本原问题 ） 有直接的解存在 。
当一个问题存在上述两个基本要素时, 设计该问题的 递归算法的方法 是：
（ 1） 把对原问题的求解设计成包含有对子问题求解的形式 。
（ 2） 设计递归出口 。
12
例 6-3 设计模拟 汉诺塔问题 求解过程的算法 。 汉诺塔问题的
描述是：设有 3根标号为 A,B,C的柱子, 在 A柱上放着 n个盘子,
每一个都比下面的略小一点, 要求把 A柱上的盘子全部移到 C柱
上, 移动的规则是,（ 1） 一次只能移动一个盘子； （ 2） 移动
过程中大盘子不能放在小盘子上面； （ 3） 在移动过程中盘子
可以放在 A,B,C的任意一个柱子上 。
问题分析,可以用递归方法求解 n个盘子的汉诺塔问题。
基本思想, 1个盘子的汉诺塔问题可直接移动。 n个盘子的汉诺
塔问题可递归表示为，首先把上边的 n-1个盘子从 A柱移到 B柱，
然后把最下边的一个盘子从 A柱移到 C柱，最后把移到 B柱的 n-1
个盘子再移到 C柱。 4个盘子汉诺塔问题的递归求解示意图如图
6-4所示。
13
图 6-4 汉诺塔问题的递归求解示意图
14
算法设计,首先，盘子的个数 n是必须的一个输入参数，对 n个盘子,
我们可从上至下依次编号为 1,2,…,n ；其次，输入参数还需有 3个柱
子的代号,我们令 3个柱子的参数名分别为 fromPeg,auxPeg和 toPeg；
最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是 n个盘
子从柱子 fromPeg借助柱子 auxPeg移动到柱子 toPeg的移动步骤，我们
设计每一步的移动为屏幕显示如下形式的信息：
Move Disk i from Peg X to Peg Y
这样，汉诺塔问题的 递归算法可设计如下,
15
void towers(int n,char fromPeg,char toPeg,char auxPeg)
{ if(n==1)
{ printf("%s%c%s%c\n","move disk 1 from peg ",
fromPeg," to peg ",toPeg);
return;
}
towers(n-1,fromPeg,auxPeg,toPeg);
printf("%s%d%s%c%s%c\n","move disk ",n,
" from peg ",fromPeg," to peg ",toPeg);
towers(n-1,auxPeg,toPeg,fromPeg);
}
16
测试主函数如下,
#include <stdio.h>
void main(void)
{
Towers(4,'A','C','B');
}
程序运行的输出信息如下：
17
Move Disk 1 from Peg A to Peg B
Move Disk 2 from Peg A to Peg C
Move Disk 1 from Peg B to Peg C
Move Disk 3 from Peg A to Peg B
Move Disk 1 from Peg C to Peg A
Move Disk 2 from Peg C to Peg B
Move Disk 1 from Peg A to Peg B
Move Disk 4 from Peg A to Peg C
Move Disk 1 from Peg B to Peg C
Move Disk 2 from Peg B to Peg A
Move Disk 1 from Peg C to Peg A
Move Disk 3 from Peg B to Peg C
Move Disk 1 from Peg A to Peg B
Move Disk 2 from Peg A to Peg C
Move Disk 1 from Peg B to Peg C
18
从程序的运行输出信息可见, 上述算法实现了递归求解汉
诺塔问题 。 递归算法把移动 n个盘子的汉诺塔问题分解为移动
n-1个盘子的汉诺塔问题, 把移动 n-1个盘子的汉诺塔问题分
解为移动 n-2个盘子的汉诺塔问题, …, 把移动 2个盘子的汉
诺塔问题分解为移动 1个盘子的汉诺塔问题 。 对于 1个盘子的
汉诺塔问题直接求解 。 在 1个盘子的汉诺塔问题解决后, 可以
解决 2个盘子的汉诺塔问题, …,在 n-1个盘子的汉诺塔问题解
决后, 可以解决 n个盘子的汉诺塔问题 。 这样 n个盘子的汉诺
塔问题最终就得以解决 。
结合本节和 6.2节的讨论, 我们可 总结如下,递归算法的
执行过程是不断地自调用, 直到到达递归出口才结束自调用
过程；到达递归出口后, 递归算法开始按最后调用的过程最
先返回的次序返回；返回到最外层的调用语句时递归算法执
行过程结束 。
19
6.4递归过程和运行时栈
对于非递归函数，调用函数在调用被调用函数前，系统要 保存 以
下两类 信息,
（ 1）调用函数的返回地址；
（ 2）调用函数的局部变量值。
当执行完被调用函数，返回调用函数前，系统首先要 恢复 调用函
数的 局部变量值,然后 返回 调用函数的 返回地址 。
递归函数被调用时，系统要作的工作和非递归函数被调用时系
统要作的工作在 形式上类同,但 保存信息的方法不同 。
递归函数被调用时，系统的运行时栈也要保存上述两类信息。
每一层递归调用所需保存的信息构成运行时栈的一个 工作记录,在
每进入下一层递归调用时，系统就建立一个新的工作记录，并把这
个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就
退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递
归函数的工作记录，所以栈顶的工作记录也称为 活动记录 。
20
6.5递归算法的效率分析
斐波那契数列 Fib(n)的递推定义是：
求第 n项斐波那契数列的 递归函数 如下：
long Fib(int n)
{ if(n == 0 || n == 1) return n; //递归出口
else return Fib(n-1) + Fib(n-2); //递归调用
}
21
用归纳法可以证明求 Fib(n)的递归 调用次数 等
于 2n-1；计算斐波那契数列的递归函数 Fib(n)的 时
间复杂度 为 O(2n)。计算斐波那契数列 Fib(n)问题，
我们也可根据公式写出 循环方式求解的函数如下,
22
long Fib2(int n)
{ long int oneBack,twoBack,current;
int i;
if(n == 0 || n == 1) return n;
else
{ oneBack = 1;
twoBack = 0;
for(i = 2; i <= n; i++)
{ current = oneBack + twoBack;
twoBack = oneBack;
oneBack = current;
}
return current;
}
}
23
上述循环方式的计算斐波那契数列的函数 Fib2(n)的时间复杂度为
O(n)。对比循环结构的 Fib2(n)和递归结构的 Fib(n)可发现,循环结构
的 Fib2(n)算法在计算第 n项的斐波那契数列时 保存了 当前已经计算得
到的 第 n-1项和第 n-2项的斐波那契数列,因此其 时间复杂度为 O(n)；
而 递归结构 的 Fib(n)算法在计算第 n项的斐波那契数列时,必须首先计
算第 n-1项和第 n-2项的斐波那契数列,而某次递归计算得出的斐波那
契数列，如 Fib(n-1),Fib(n-2)等 无法保存,下一次要用到时还需要
重新递归计算，因此其 时间复杂度为 O(2n) 。
24
6.6递归算法到非递归算法的转换
有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如
汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一
般来说，存在如下 两种情况的递归算法 。
（ 1）存在 不借助堆栈的循环结构的非递归算法,如阶乘计算问题、斐
波那契数列的计算问题、折半查找问题等。
（ 2）存在 借助堆栈的循环结构的非递归算法,所有递归算法都可以借
助堆栈转换成循环结构的非递归算法，如下边例 6-4设计的汉诺塔问题的
借助堆栈的循环结构的非递归算法。
对于第一种情况，可以直接选用循环结构的算法。
对于第二种情况，可以把递归算法转换成相应的非递归算法,此时
有两种转换方法,一种方法是借助堆栈,用非递归算法形式化模拟递归
算法的执行过程； 另一种方法是 根据要求解问题的特点,设计借助堆栈
的循环结构算法 。这两种方法都需要使用堆栈，这是因为堆栈的后进先
出特点正好和递归函数的运行特点相吻合。下面讨论的例 6-4是第二种情
况下的第一种转换方法的例子
25
6.7设计举例
6.7.1 一般递归算法设计举例
例 6-5 设计一个输出如下形式数值的递归算法 。
n n n,.,n
......
3 3 3
2 2
1
26
问题分析,该问题可以看成由两部分组成：一部分是输出一
行值为 n的数值；另一部分是原问题的子问题, 其参数为 n-1。
当参数减到 0时不再输出任何数据值, 因此递归的出口是当参
数 n≤ 0时空语句返回 。
void Display(int n)
{ int i;
for(i = 1; i <= n; i++)
printf("%d ",n);
printf("%\n");
if(n > 0) Display(n - 1);
}
27
例 6-6 设计求解 委员会问题 的算法 。 委员会问题是：从一个
有 n个人的团体中抽出 k (k≤n) 个人组成一个委员会, 计算
共有多少种构成方法 。
问题分析,从 n个人中抽出 k(k≤n) 个人的问题是一个组合
问题 。 把 n个人固定位置后, 从 n个人中抽出 k个人的问题可
分解为两部分之和：第一部分是第一个人包括在 k个人中,
第二部分是第一个人不包括在 k个人中 。 对于第一部分, 则
问题简化为从 n-1个人中抽出 k-1个人的问题；对于第二部
分, 则问题简化为从 n-1个人中抽出 k个人的问题 。 图 6-7给
出了 n=5,k=2时问题的分解示意图 。
28
29
当 n=k或 k=0时，该问题可直接求解，数值均为 1，这
是算法的递归出口。因此，委员会问题的 递推定义式 为：
int Comm(int n,int k)
{
if(n < 1 || k < 0 || k > n) return 0;
if(k == 0) return 1;
if(n == k) return 1;
return Comm(n-1,k-1) + Comm(n-1,k);
}
30
例 6-7 求两个正整数 n和 m最大公约数的递推定义式为：
要求：
（ 1） 编写求解该问题的递归算法；
（ 2） 分析当调用语句为 Gcd(30,4)时算法的
执行过程和执行结果；
（ 3） 分析当调用语句为 Gcd(97,5)时算法的
执行过程和执行结果；
（ 4） 编写求解该问题的循环结构算法 。
31
解：
递归算法如下：
int Gcd(int n,int m)
{ if(n < 0 || m < 0) exit(0);
if(m == 0) return n;
else if(m > n) return Gcd(m,n);
else return Gcd(m,n % m);
}
32
1.调用语句为 Gcd(30,4)时, 因 m<n,递归调用 Gcd(4,2)；
因 m<n,递归调用 Gcd(2,0)；因 m=0,到达递归出口, 函
数最终返回值为 n=2,即 30和 4的最大公约数为 2
2.调用语句为 Gcd(5,97)时, 因 m>n,递归调用 Gcd(97,5)；
因 m<n,递归调用 Gcd(5,2)；因 m<n,递归调用 Gcd(2,1)；
因 m<n,递归调用 Gcd(1,0)；因 m=0,到达递归出口, 函
数最终返回值为 n=1,即 5和 97的最大公约数为 1。
分析：
存在算法调用自己的情况：
若一个算法直接的或间接的 调用自己本身,则称这
个算法是递归算法。
（ 1） 问题的定义是递推的
阶乘函数的 常见定义 是：
6.1递归的概念
3
也可定义为：
写成函数形式，则为：
这种函数定义的方法是 用阶乘函数
自己本身定义了阶乘函数,称公式（ 6
– 3）是阶乘函数的 递推定义式 。
4
（ 2）问题的解法存在自调用
一个典型的例子是在 有序数组中 查找一个数
据元素是否存在的 折半查找算法 。
5
6.2递归算法的执行过程
例 6-1 给出按照公式 6-3计算阶乘函数的递归算法,
并给出 n = 3时递归算法的执行过程 。
设计：按照公式 6-3计算阶乘函数的递归算法如下：
long int Fact(int n)
{ int x;
long int y;
if(n < 0) /*(n < 0时阶乘无定义 */
{ printf(,参数错 ！, );
return -1; }
if(n == 0) return 1;
else {y = Fact(n - 1); /*递归调用 */
return n * y; }
}
6
为说明该递归算法的执行过程，设计主函数如下
void main(void)
{
long int fn;
fn = Fact(3);
}
主函数用 实参 n = 3调用了递归算法 Fact(3)，而 Fact(3)要通
过 调用 Fact(2),Fact(2)要通过 调用 Fact(1),Fact(1)要通过
调用 Fact(0)来得出计算结果。 Fact(3)的递归调用过程如图 6-2
所示，其中,实线箭头表示函数调用，虚线箭头表示函数返回,
此函数在返回时函数名将带回返回值 。
7
例 6-2 给出在 有序数组 a中查找数据元素 x是否存在 的递归算法，
并给出如图 6-1所示实际数据的递归算法的执行过程。
设计,算法的参数包括,有序数组 a，要查找的数据元素 x，
数组下界下标 low，数组上界下标 high。当在数组 a中查找到数据
元素 x时函数返回数组 a的下标 ；当在数组 a中查找不到数据元素 x
时函数返回 -1。
8
递归 算法如下：
int BSearch(int a[],int x,int low,int high)
{ int mid;
if(low > high) return -1; /*查找不成功 */
mid = (low + high) / 2;
if(x == a[mid]) return mid; /*查找成功 */
else if(x < a[mid])
return BSearch(a,x,low,mid-1); /*在下半区查找 */
else
return BSearch(a,x,mid+1,high); /*在上半区查找 */
}
9
测试主函数设计如下：
# include <stdio.h>
main(void)
{ int a[] = {1,3,4,5,17,18,31,33};
int x = 17;
int bn;
bn = BSearch(a,x,0,7);
if(bn == -1) printf("x不在数组 a中 ");
else printf("x在数组 a的下标 %d中 ",bn);
}
10
BSearch(a,x,0,7)的递归调用过程如图 6-3所示，
其中,实箭头 表示函数 调用, 虚箭头 表示函数的 返回值 。
11
6.3递归算法的设计方法
递归算法既是一种有效的 算法设计 方法, 也是一种有效的 分析问题 的方
法 。 递归算法求解问题的 基本思想 是：对于一个较为复杂的问题, 把原问题
分解成若干个相对简单且类同的子问题, 这样较为复杂的原问题就变成了相
对简单的子问题；而简单到一定程度的子问题可以直接求解；这样, 原问题
就可递推得到解 。
并不是每个问题都适宜于用递归算法求解 。 适宜于用递归算法求解的问
题的 充分必要条件 是：
（ 1） 问题具有某种可借用的类同自身的子问题描述的性质；
（ 2） 某一有限步的子问题 （ 也称作本原问题 ） 有直接的解存在 。
当一个问题存在上述两个基本要素时, 设计该问题的 递归算法的方法 是：
（ 1） 把对原问题的求解设计成包含有对子问题求解的形式 。
（ 2） 设计递归出口 。
12
例 6-3 设计模拟 汉诺塔问题 求解过程的算法 。 汉诺塔问题的
描述是：设有 3根标号为 A,B,C的柱子, 在 A柱上放着 n个盘子,
每一个都比下面的略小一点, 要求把 A柱上的盘子全部移到 C柱
上, 移动的规则是,（ 1） 一次只能移动一个盘子； （ 2） 移动
过程中大盘子不能放在小盘子上面； （ 3） 在移动过程中盘子
可以放在 A,B,C的任意一个柱子上 。
问题分析,可以用递归方法求解 n个盘子的汉诺塔问题。
基本思想, 1个盘子的汉诺塔问题可直接移动。 n个盘子的汉诺
塔问题可递归表示为，首先把上边的 n-1个盘子从 A柱移到 B柱，
然后把最下边的一个盘子从 A柱移到 C柱，最后把移到 B柱的 n-1
个盘子再移到 C柱。 4个盘子汉诺塔问题的递归求解示意图如图
6-4所示。
13
图 6-4 汉诺塔问题的递归求解示意图
14
算法设计,首先，盘子的个数 n是必须的一个输入参数，对 n个盘子,
我们可从上至下依次编号为 1,2,…,n ；其次，输入参数还需有 3个柱
子的代号,我们令 3个柱子的参数名分别为 fromPeg,auxPeg和 toPeg；
最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是 n个盘
子从柱子 fromPeg借助柱子 auxPeg移动到柱子 toPeg的移动步骤，我们
设计每一步的移动为屏幕显示如下形式的信息：
Move Disk i from Peg X to Peg Y
这样，汉诺塔问题的 递归算法可设计如下,
15
void towers(int n,char fromPeg,char toPeg,char auxPeg)
{ if(n==1)
{ printf("%s%c%s%c\n","move disk 1 from peg ",
fromPeg," to peg ",toPeg);
return;
}
towers(n-1,fromPeg,auxPeg,toPeg);
printf("%s%d%s%c%s%c\n","move disk ",n,
" from peg ",fromPeg," to peg ",toPeg);
towers(n-1,auxPeg,toPeg,fromPeg);
}
16
测试主函数如下,
#include <stdio.h>
void main(void)
{
Towers(4,'A','C','B');
}
程序运行的输出信息如下：
17
Move Disk 1 from Peg A to Peg B
Move Disk 2 from Peg A to Peg C
Move Disk 1 from Peg B to Peg C
Move Disk 3 from Peg A to Peg B
Move Disk 1 from Peg C to Peg A
Move Disk 2 from Peg C to Peg B
Move Disk 1 from Peg A to Peg B
Move Disk 4 from Peg A to Peg C
Move Disk 1 from Peg B to Peg C
Move Disk 2 from Peg B to Peg A
Move Disk 1 from Peg C to Peg A
Move Disk 3 from Peg B to Peg C
Move Disk 1 from Peg A to Peg B
Move Disk 2 from Peg A to Peg C
Move Disk 1 from Peg B to Peg C
18
从程序的运行输出信息可见, 上述算法实现了递归求解汉
诺塔问题 。 递归算法把移动 n个盘子的汉诺塔问题分解为移动
n-1个盘子的汉诺塔问题, 把移动 n-1个盘子的汉诺塔问题分
解为移动 n-2个盘子的汉诺塔问题, …, 把移动 2个盘子的汉
诺塔问题分解为移动 1个盘子的汉诺塔问题 。 对于 1个盘子的
汉诺塔问题直接求解 。 在 1个盘子的汉诺塔问题解决后, 可以
解决 2个盘子的汉诺塔问题, …,在 n-1个盘子的汉诺塔问题解
决后, 可以解决 n个盘子的汉诺塔问题 。 这样 n个盘子的汉诺
塔问题最终就得以解决 。
结合本节和 6.2节的讨论, 我们可 总结如下,递归算法的
执行过程是不断地自调用, 直到到达递归出口才结束自调用
过程；到达递归出口后, 递归算法开始按最后调用的过程最
先返回的次序返回；返回到最外层的调用语句时递归算法执
行过程结束 。
19
6.4递归过程和运行时栈
对于非递归函数，调用函数在调用被调用函数前，系统要 保存 以
下两类 信息,
（ 1）调用函数的返回地址；
（ 2）调用函数的局部变量值。
当执行完被调用函数，返回调用函数前，系统首先要 恢复 调用函
数的 局部变量值,然后 返回 调用函数的 返回地址 。
递归函数被调用时，系统要作的工作和非递归函数被调用时系
统要作的工作在 形式上类同,但 保存信息的方法不同 。
递归函数被调用时，系统的运行时栈也要保存上述两类信息。
每一层递归调用所需保存的信息构成运行时栈的一个 工作记录,在
每进入下一层递归调用时，系统就建立一个新的工作记录，并把这
个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就
退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递
归函数的工作记录，所以栈顶的工作记录也称为 活动记录 。
20
6.5递归算法的效率分析
斐波那契数列 Fib(n)的递推定义是：
求第 n项斐波那契数列的 递归函数 如下：
long Fib(int n)
{ if(n == 0 || n == 1) return n; //递归出口
else return Fib(n-1) + Fib(n-2); //递归调用
}
21
用归纳法可以证明求 Fib(n)的递归 调用次数 等
于 2n-1；计算斐波那契数列的递归函数 Fib(n)的 时
间复杂度 为 O(2n)。计算斐波那契数列 Fib(n)问题，
我们也可根据公式写出 循环方式求解的函数如下,
22
long Fib2(int n)
{ long int oneBack,twoBack,current;
int i;
if(n == 0 || n == 1) return n;
else
{ oneBack = 1;
twoBack = 0;
for(i = 2; i <= n; i++)
{ current = oneBack + twoBack;
twoBack = oneBack;
oneBack = current;
}
return current;
}
}
23
上述循环方式的计算斐波那契数列的函数 Fib2(n)的时间复杂度为
O(n)。对比循环结构的 Fib2(n)和递归结构的 Fib(n)可发现,循环结构
的 Fib2(n)算法在计算第 n项的斐波那契数列时 保存了 当前已经计算得
到的 第 n-1项和第 n-2项的斐波那契数列,因此其 时间复杂度为 O(n)；
而 递归结构 的 Fib(n)算法在计算第 n项的斐波那契数列时,必须首先计
算第 n-1项和第 n-2项的斐波那契数列,而某次递归计算得出的斐波那
契数列，如 Fib(n-1),Fib(n-2)等 无法保存,下一次要用到时还需要
重新递归计算，因此其 时间复杂度为 O(2n) 。
24
6.6递归算法到非递归算法的转换
有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如
汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一
般来说，存在如下 两种情况的递归算法 。
（ 1）存在 不借助堆栈的循环结构的非递归算法,如阶乘计算问题、斐
波那契数列的计算问题、折半查找问题等。
（ 2）存在 借助堆栈的循环结构的非递归算法,所有递归算法都可以借
助堆栈转换成循环结构的非递归算法，如下边例 6-4设计的汉诺塔问题的
借助堆栈的循环结构的非递归算法。
对于第一种情况，可以直接选用循环结构的算法。
对于第二种情况，可以把递归算法转换成相应的非递归算法,此时
有两种转换方法,一种方法是借助堆栈,用非递归算法形式化模拟递归
算法的执行过程； 另一种方法是 根据要求解问题的特点,设计借助堆栈
的循环结构算法 。这两种方法都需要使用堆栈，这是因为堆栈的后进先
出特点正好和递归函数的运行特点相吻合。下面讨论的例 6-4是第二种情
况下的第一种转换方法的例子
25
6.7设计举例
6.7.1 一般递归算法设计举例
例 6-5 设计一个输出如下形式数值的递归算法 。
n n n,.,n
......
3 3 3
2 2
1
26
问题分析,该问题可以看成由两部分组成：一部分是输出一
行值为 n的数值；另一部分是原问题的子问题, 其参数为 n-1。
当参数减到 0时不再输出任何数据值, 因此递归的出口是当参
数 n≤ 0时空语句返回 。
void Display(int n)
{ int i;
for(i = 1; i <= n; i++)
printf("%d ",n);
printf("%\n");
if(n > 0) Display(n - 1);
}
27
例 6-6 设计求解 委员会问题 的算法 。 委员会问题是：从一个
有 n个人的团体中抽出 k (k≤n) 个人组成一个委员会, 计算
共有多少种构成方法 。
问题分析,从 n个人中抽出 k(k≤n) 个人的问题是一个组合
问题 。 把 n个人固定位置后, 从 n个人中抽出 k个人的问题可
分解为两部分之和：第一部分是第一个人包括在 k个人中,
第二部分是第一个人不包括在 k个人中 。 对于第一部分, 则
问题简化为从 n-1个人中抽出 k-1个人的问题；对于第二部
分, 则问题简化为从 n-1个人中抽出 k个人的问题 。 图 6-7给
出了 n=5,k=2时问题的分解示意图 。
28
29
当 n=k或 k=0时，该问题可直接求解，数值均为 1，这
是算法的递归出口。因此，委员会问题的 递推定义式 为：
int Comm(int n,int k)
{
if(n < 1 || k < 0 || k > n) return 0;
if(k == 0) return 1;
if(n == k) return 1;
return Comm(n-1,k-1) + Comm(n-1,k);
}
30
例 6-7 求两个正整数 n和 m最大公约数的递推定义式为：
要求：
（ 1） 编写求解该问题的递归算法；
（ 2） 分析当调用语句为 Gcd(30,4)时算法的
执行过程和执行结果；
（ 3） 分析当调用语句为 Gcd(97,5)时算法的
执行过程和执行结果；
（ 4） 编写求解该问题的循环结构算法 。
31
解：
递归算法如下：
int Gcd(int n,int m)
{ if(n < 0 || m < 0) exit(0);
if(m == 0) return n;
else if(m > n) return Gcd(m,n);
else return Gcd(m,n % m);
}
32
1.调用语句为 Gcd(30,4)时, 因 m<n,递归调用 Gcd(4,2)；
因 m<n,递归调用 Gcd(2,0)；因 m=0,到达递归出口, 函
数最终返回值为 n=2,即 30和 4的最大公约数为 2
2.调用语句为 Gcd(5,97)时, 因 m>n,递归调用 Gcd(97,5)；
因 m<n,递归调用 Gcd(5,2)；因 m<n,递归调用 Gcd(2,1)；
因 m<n,递归调用 Gcd(1,0)；因 m=0,到达递归出口, 函
数最终返回值为 n=1,即 5和 97的最大公约数为 1。
分析：
