第　3　章
递归算法 
在计算机程序设计中,若一个函数在其函数体内又直接或间接调用了自身,则称之为
递归函数。递归的例子在生活中比比皆是,如“从前有座山,山里有个庙,庙里有个老和
尚,老和尚给小和尚讲故事……”,新闻联播中主播身后背景中的电视画面又出现了主播, 
在两面镜子中间看自己的像等。
要理解递归,仅了解递归的概念远远不够,需要从本质上掌握递归的特性,递归的使
用场景以及递归存在的局限,才能够看懂、写出递归程序。因为递归是在函数内部调用其
自身,所以递归要解决的必定是可重复性问题。计算机程序的实现是有穷的,需要在一定
时间内执行完毕,故而递归程序不可能一直执行,必须在某个时刻到达出口,这就决定了
问题的规模是逐渐递减的。从上述分析可以得出递归的本质特性如下。
(1)问题及其子问题有相同的结构。
(2)子问题的规模逐渐递减。
(3)有终止条件作为出口。
用递归算法解决问题时,程序简洁清晰,易于理解,但递归程序调试复杂,真正理解相
当不易。需要注意的问题是,由于函数调用的开销和子问题的重复求解,递归程序效率不
高。因此,处理复杂问题时,递归程序往往需要与动态规划等算法结合使用。
3.1　汉诺塔问题
汉诺塔问题是心理学实验研究常用的任务之一,在医学临床上也常将汉诺塔任务用
于检查脑损伤者的执行功能。汉诺塔问题主要涉及3根高度相同的柱子和大小互不相同
的一套64个圆盘,3根柱子分别用起始柱A、辅助柱B及目标柱C代表。汉诺塔问题的
目标是通过辅助柱B,将64个圆盘从起始柱A 移动到目标柱C上。移动过程中,每次只
能移动一个盘子,所有柱子上的盘子必须小盘在上、大盘在下。
3.1.1 汉诺塔问题解题思路分析
假设初始时盘子依序放在A 柱上,盘子由1开始从上向下编号,先对问题进行必要
分析获得问题的通解。
(1)n=1时,只有一个盘子,问题可以直接解决。

序号盘子移动过程
第1次1号A→C 
合计1次

(2)n=2时,2个盘子需要借助其他柱子才能完成。

序号盘子移动过程
第1次1号A→B 
第2次2号A→C 
第3次1号B→C 
合计3次

(3)n=3时,移动次数明显增多。

序号盘子移动过程
第1次1号A→C 
第2次2号A→B 
第3次1号C→B 
第4次3号A→C 
第5次1号B→A 
第6次2号B→C 
第7次1号A→C 
合计7次

(4)n=4时,移动次数为15 次。
7,…,
n 

以此类推,得到各项对应的形式为:F1=1,F2=3,F3=Fn 
=2Fn-1+1=21,当n=64 时,F64=264-1=18446744073709551615,即使移动一次用一秒,移动完成也
要五千多亿年。

要想理解递归算法解决汉诺塔问题,关键在于得“麻痹”自己,相信自己像神笔马良一
样会使用“神笔”,可以将问题分为3个大的步骤解决,如图3-1所示。

(1)将A柱顶端的n-1个盘子通过施展“神笔”借助C柱移动到B柱上,此时A柱
只剩最大一个盘子,B柱有n-1个盘子,C柱为空。
(2)第二步非常简单,直接将最大的盘子从A柱移动到C柱。
(3)将B柱上的n-1个盘子再次施展“神笔”,借助A柱移动到C柱上,至此大功
告成! 
在此过程中,始终让人耿耿于怀的莫过于“神笔”功能是如何施展的。这个“神笔”的
施展正是递归的精华所在。两次施展“神笔”处理的盘子数目都是n-1个,规模小于原始

43

的问题的规模,求解方法却与原始问题相同。所以,“神笔”的施展与
n 
个盘子时的处理方
法相同,只需将图3-1中的
n 
变为n-1即可。处理n-1个盘子时,可令
m 
=n-1,问题

(1)就变成了将
m 
个盘子从A柱借助C柱移动到B柱的过程,问题(3)则是将
m 
个盘子
从B柱借助A柱移动到C柱的过程。对于
m 
个盘子的处理,与
n 
个盘子处理的流程完
全一致,这样一直递推下去,直至一个盘子时结束。
图3-1 汉诺塔解题3步示意图

3.2 
汉诺塔问题代码分析
1.
求解汉诺塔问题主体功能的是Hano() 函数,main() 函数用于测试,MoveDishes() 函
数用于输出移动圆盘的提示信息。

MoveDishes() 函数的主要功能是输出实际移动圆盘时的提示信息,同时统计移动圆
盘的总次数。因为函数执行后需要将总移动次数返回到Hano() 函数,供下次计数使用, 
所以代表移动次数的count变量必须为指针变量。

Hano() 函数包括5个参数,B为辅助

n 
为圆盘的个数,A为起始柱对应的标识字母,
柱对应的标识字母,C为目标柱对应的标识字母,指针count用于统计移动次数。当只有
一个圆盘时,直接将圆盘从A柱移动到C柱;当圆盘数多于一个时,需要施展“神笔”进行
“三步走”,先将n-1个圆盘从A柱借助C柱移动到B柱,然后将最大圆盘从A柱移动到
C柱,最后将n-1个圆盘从B柱借助A柱移动到C柱。实现代码如下。

44

45 
#include<iostream> 
using namespace std; 
void MoveDishes(int disks, char source, char dest, int* count) 
{ 
(*count)++;//移动次数加1 
cout << "第" << (*count) << "次移动: "; 
cout<< disks << "号圆盘" << source << " -> " << dest << endl; 
}v
oid Hano(int n, char A, char B, char C, int* count) 
{ 
if (n == 1) 
MoveDishes(n, A, C, count); 
else 
{ 
Hano(n - 1, A, C, B, count); 
MoveDishes(n, A, C, count); 
Hano(n - 1, B, A, C, count); 
} 
}i
nt main() 
{ 
int count = 0; 
Hano(3, 'A', 'B', 'C', &count); 
return 0; 
}
当圆盘个数为3时,运行结果如下。
3.2　全排列问题
排列就是将元素(或符号)按照确定的顺序进行重排,重排后的每一个顺序称为一个
排列。例如,对于元素集S={1,2,3}而言,可获得6个排列p1=(1,2,3),p2=(1,3,2), 
p3=(2,1,3),p4=(2,3,1),p5=(3,1,2),p6=(3,2,1)。从n 个不重复元素中任取m 
个元素,这m 个元素构成的所有不同排列的个数称为排列数,记为Am 
n 或A (n,m ),计算
公式如式(3.1)所示。
Am 
n =n(n -1)(n -2)…(n -m +1)= n! 
(n -m )! (3.1)

46 
其中,! 表示阶乘。以A36
为例,共有3个位置可以放置元素,第1个位置所有6个元素都
可以放置,第2个位置只有5个元素可以放置,第3个位置只有4个元素可以放置,可构
成的排列数为A36 
=6×5×4= 6! 
(6-3)!=720 
6 =120。
当m =n 时,构成的排列称为全排列。可以通过递归来枚举生成排列树的方式求解
全排列问题。假定待处理的元素集合为S={s1,s2,…,sn },令Si=S-si,用p(S)表示
S 的全排列,(si)p(Si)表示由Si 的每一个排列加上前缀si 构成的排列,则全排列可用
式(3.2)进行描述。
p(S)= (s), n=1 
(s1)p(S1),(s2)p(S2),…,(sn)p(Sn), n>1 { (3.2) 
图3-2给出了集合为{1,2,3,4}时的排列枚举树。
图3-2 集合为{1,2,3,4}时的全排列枚举树
3.2.1 无重复元素的全排列
对一个无重复元素的有限集或其子集进行全排列时,可以按照最朴素的方法以递归
方式进行求解。

47 
1)解题思路
求有n 个不重复元素的全排列的基本思路:先取出集合中的第1个元素s1 作为排列
的第1位,将其余的n-1个元素进行全排列;对n-1个元素进行全排列时,同样先确定
第1位,然后其余n-2个元素进行全排列,以此类推,直至集合中只余一个元素时结束。
从分析过程中可以看出,问题和子问题的求解方法是相同的,与原问题相比,子问题的规
模不断缩小;当n=1时,处理结束。这是典型的递归求解问题。
2)辅助函数
为了便于处理,假定需要进行排列的元素均为字符型。建立Swap()函数,该函数用
于交换集合中的两元素。函数有3个参数,list[]为构成排列的字符元素集合,m 和n 为
待交换值的两个元素对应的下标。 
void Swap(char list[], int m, int n) 
{ 
char temp = list[m]; 
list[m] = list[n]; 
list[n] = temp; 
} 
3)朴素全排列函数
实现朴素全排列功能的函数为NativeAllPermutation()。NativeAllPermutation()函
数为递归函数,实现从list[]集合中start至last范围内元素的全排列,使用current表示
本次递归过程中的当前位置。函数有4个参数,list[]为元素集合,start为起始位置下标
(输出时使用),current为当前位置下标(递归时使用),last为终止位置下标。
当前递归位置current到达last时,说明已经实现了某个排列,到达出口,可以输出该
排列。未到达出口时,从current至last,依次交换i 与current位置的元素,然后再进行
全排列。实现代码如下。 
void NativeAllPermutation(char list[], int start, int current, int last) 
{ 
int i; 
if (current == last) //当前位置到达last,实现了一个排列,输出该排列 
{ 
for (i = start; i <= last; i++) 
cout << list[i]; 
cout << endl; 
} 
else 
{ 
for (i = current; i <= last; i++) 
{ 
Swap(list, current, i); 
//交换位置后,输出list[j]不变、后面的字母改变的所有排列 
NativeAllPermutation(list, start, current + 1, last);

48 
//处理交换后的全排列之后,还需要还原准备下一次交换 
Swap(list, current, i); //还原非常重要 
} 
} 
}
至此,已经实现了n 个不重复元素的全排列。但元素集合中有重复元素的情况尚未
解决,例如元素集合为{a,b,b}时,交换后会出现两个值相同的重复排列。因此,需要解决
全排列的去重问题,需要对当前算法进一步改进。
3.2.2 有重复元素的全排列
若元素集合中存在重复元素,生成全排列时需要解决重复问题,例如abb形式只应输
出一次。生成消除重复元素全排列的主体函数是AllPermutation()函数,参数与朴素全
排列函数NativeAllPermutation()相同,处理流程基本一致,唯一变化的是在进行进一步
递归生成排列前调用了NeedSwap()函数。
1)辅助函数
NeedSwap()函数用于判定当前元素与之前的元素间是否存在重复,是实现消除重复
全排列的关键。该函数有3个参数,list[]、current和i,作用和意义与朴素全排列函数
NativeAllPermutation()相同。去重全排列的根本在于当前元素只需要与它前面出现的
非重复字符交换。因此,NeedSwap()函数增加了判断条件,判定两个待交换元素的值是
否相同,若相等则表示元素值重复无须交换,不相同则应进行交换。 
bool NeedSwap(char list[], int current, int i) 
{ 
int j; 
//若[current, i) 里存在与a[i]相同的元素,说明该排列已经存在,不进行交换 
for (j = current; j < i; j++) 
if (list[j] == list[i]) //list[i]是等待被交换的元素 
return false; 
return true; 
} 
2)整合后全排列代码
本部分代码将朴素全排列函数与消除重复情况的全排列函数合并到同一段代码中, 
在主函数中进行测试。 
#include <iostream> 
#include <cstring> 
using namespace std; 
void Swap(char list[], int m, int n) //交换数组A 中下标为m 和n 的元素
{ 
char temp = list[m]; 
list[m] = list[n];

49 
list[n] = temp; 
}v
oid NativeAllPermutation(char list[], int start, int current, int last) 
{ 
int i; 
if (current == last) 
{ 
for (i = start; i <= last; i++) 
cout << list[i]; 
cout << endl; 
} 
else 
{ 
for (i = current; i <= last; i++) 
{ 
Swap(list, current, i); 
//交换位置后,输出以list[j]不变,后面的字母改变的所有排列 
NativeAllPermutation(list, start, current + 1, last); 
Swap(list, current, i); //还原 
} 
} 
}b
ool NeedSwap(char list[], int current, int i)//list[i]是等待被交换的元素
{ 
int j; 
//若[current, i)内存在和list[i]相同的元素,说明该排列已经存在 
for (j = current; j < i; j++) 
if (list[j] == list[i]) 
return false; 
return true; //不存在,则j == i,需要交换
} //消除重复情况的全排列函数
void AllPermutation(char list[], int start, int current, int last) 
{ 
int i; 
if (current == last) //到达序列结尾,递归终止 
{ 
for (i = start; i <= last; i++) 
cout << list[i]; 
cout << endl; 
} 
for (i = current; i <= last; i++) //从current 至尾依次交换元素,生成全排列 
{ 
if (!NeedSwap(list, current, i)) //重复则无须交换

50 
continue; 
Swap(list, current, i); 
AllPermutation(list, start, current + 1, last); 
//恢复原状以便进行下一轮交换:确保仍为交换之前的序列 
Swap(list, current, i); 
} 
}i
nt main() 
{ 
const int MAX_CHARS = 101; 
char str[MAX_CHARS]; 
int len, start, k, current; 
cin >> str >> start >> k; 
len = strlen(str); 
len = (len <= MAX_CHARS - 1) ? len : (MAX_CHARS - 1); 
current = start; 
//初始时current 与start 值相同,current 在递归过程中不断变化 
NativeAllPermutation(str, start, current, start + k - 1); 
//AllPermutation(str, start, current, start + k - 1); 
return 0; 
} 
3)测试数据及运行结果
(1)无重复情况。
当输入数据为abcdef13时,运行结果如下(无重复情况)。
(2)有重复情况。
当输入数据为abccd13时,运行结果如下(有重复)。
3.3　因数分解问题
正整数S 可表示为若干个正整数的乘积,即S=s1·s2·…·sn ,其中各个因子构成
一个递增序列,即s1≤s2≤s3≤…≤sn ,称为S 的因数分解。每一种s1·s2·…·sn 称为
S 的一个分解,需要注意的是,s=S 也是一种分解。例如,4,8,12和24的分解数分别为
2,3,4和7,分解过程如下。

4=1×4 
=2×2 

8=1×8 
=2×4 
=2×2×2 

12=1×12 
=2×6 
=2×2×3 
=3×4 

24=1×24 
=2×12 
=2×2×6 
=2×2×2×3 
=2×3×4 
=3×8 
=4×6 

3.1 
因子递增方式递归求解
3.
令Si=S/(s2·…·i), 对
S 
进行分解时,其分解过程如下。

s1· 
s
(1)
S 
自身算一种分解
。


(2)剩余分解可以通过2~ S范围内的每一个整数
k 
进行试除。
①若si=
k 
为
S 
的因子,则寻找到一个新的分解s1· s2·…·si×Si。
②同时还应该注意到,Si 
仍有可能含最小因子不小于si 
=
k 
分解,需要对Si 
从si= 
k 
开始继续分解。
图3-3给出了正整数4,8,12,24 从2开始进行因数分解的示意图。


图3-3 正整数4,8,12,24 从2开始进行因数分解的示意图

以24 为例,其因数分解过程如下。
(1)24 自身是一种分解,因此获得第1种分解24=24 。
取k=2,3,4(因为4<24<5)分别试除进行分解,递增试除保证了各个因子间是递

51

52 
增的,而且不会出现重复分解。
(2)当s1=k=2时,4种分解如下。
①S1=S/s1=24/2=12,获得第2种分解S=s1·S1,即24=2×12。
②S1 可进一步进行分解,取s2=k=2,S2=S/(s1·s2)=24/(2×2)=6,获得第3 
种分解S=s1 ·s2 ·S2,即24=2×2×6;S2 可进一步进行分解,取s3 =k=2,S3 = 
S/(s1·s2·s3)=3,获得第4种分解S=s1·s2·s3·S3,即24=2×2×2×3。
③S1 可进一步进行分解,取s2=k+1=3,S2=S/(s1·s2)=4,获得第5种分解S= 
s1·s2·S2,即24=2×3×4。
(3)当s1=k=3时,S1=S/s1=24/3=8,获得第6种分解S=s1·S1,即24=3×8。
(4)当s1=k=4时,S1=S/s1=24/4=6,获得第7种分解S=s1·S1,即24=4×6。
3.3.2 子问题分解方式递归求解
第2种分解方法主要是通过对问题的分析,获得子问题的表述,根据递归表达式来进
行求解。3.3.1节通过试除法,利用2~ S 的因子获取某个分解。也可以从S 出发,以因
子递减方式获得S 的各个分解。S 的分解因数问题N (S,m )的递归表达式如式(3.3) 
所示。
N (S,m )= 
1, S =1 
0, m =1 
N (S,m -1)+N (S/m ,m ), m |S 
N (S,m -1), m S 
ì
.
í
... 
..
. 
(3.3) 
其中,m|S 表示S 能被m 整除,m S 表示S 不能被m 整除。
3.3.3 分解因数问题代码分析
GetFactorNumbers1()函数使用因子递增方式进行分解因数。函数有两个参数,n 是
待分解的数值,m 是分解的起始值(一般从2开始,即m 的初值为2)。函数在进行因数分
解时,①将因数为自身的情况计入统计过程;②当重复分解至1时,分解过程结束;③未分
解至1时,用循环变量i 从2到n 逐个遍历进行试除,若试除成功则将n/i 从i 开始进一
步分解。实现代码如下。 
#include<iostream> 
using namespace std; 
int GetFactorNumbers1(int n, int m) //从2 开始遍历所有可能的分解
{ 
int ans = 1; //自身算一种,为1 时不算 
if (n == 1) 
return 0; 
for (int i = m; i * i <= n; i++) 
{ 
if (n % i == 0)

53 
ans += GetFactorNumbers1(n / i, i); 
} 
return ans; 
}
GetFactorNumbers2()函数使用子问题分解方式进行分解因数。函数有两个参数,n 
是待分解的数值,m 是分解的起始值(代表要分解的(疑似)最大因子,一般从n 开始,逐
渐递减至1)。函数在进行因数分解时,若被分解的数为1时,只有一种分解方式;若最大
因子为1时,则返回0;若m 为n 的因子,则进行递归分解并统计解的总和;若m 不为n 
的因子,则从m -1开始继续尝试新的分解过程。实现代码如下。 
int GetFactorNumbers2(int n, int m) 
{ 
if (n == 1) 
return 1; //若分解的数字为1 
if (m == 1) 
return 0; //若最大因子为1 
//如果m 确实是n 的因子,进行递归调用,并将分解种数相加 
if (n % m == 0) 
{ 
int c1 = GetFactorNumbers2(n, m - 1); 
int c2 = GetFactorNumbers2(n / m, m); 
return c1 + c2; 
} 
//m 不为n 的因子,尝试将m-1 作为最大因子 
return GetFactorNumbers2(n, m - 1); 
}
int main() 
{ 
int n, m1, m2; 
int count; 
cin >> count; 
while (count--) 
{ 
cin >> n; 
m1 = GetFactorNumbers1(n, 2); 
m2 = GetFactorNumbers2(n, n); 
cout << m1 << " " << m2 << endl; 
} 
return 0; 
}
测试数据及运行结果如下。

54 
当输入两个测试数据:12和24时,12有4种分解方式,24有7种分解方式,运行结
果如下。
3.4　分形图形
分形算法是现代数学的一个新分支,与动力系统的混沌理论交叉结合,相辅相成。在
图3-4 芒德球
一定条件下,事物在形态、结构、信息、功能、时间或能量等
在某方面表现出与整体的相似性。分形是指事物的多重
自相似性,可以是以自然形态存在的,也可以是人为设
计的。美
籍法国数学家B.B.Mandelbrot在1975年首先提出
了分形几何的概念。计算机的应用和普及,使人们真正了
解了分形。2009年,英国分形爱好者DanielWhite创造出
3D分形影像,并将之命名为芒德球,如图3-4所示。尽管
芒德球外形极其烦琐,但却是由基于复数的基础算法得
出的。
3.4.1 盒分形思路分析
本节主要研究盒分形。盒分形的规模用度表述,盒分形定义如下。
(1)度为1的盒子分形如下。 
X
(2)度为2的盒子分形如下。 
X X 
X 
X X 
(3)度为n 的盒分形如下。
用B(n-1)表示度为n-1的盒分形,则度为n 的盒分形可用式(3.4)表示。
B(n -1) B(n -1) 
B(n -1) 
B(n -1) B(n -1) 
(3.4) 
假设输出符号为X,度为3的盒分形输出如下。

55 
X X X X 
X X 
X X X X 
X X 
X 
X X 
X X X X 
X X 
X X X X 
度为n 的盒分形的可用边长为3n-1的正方形表示其坐标,如图3-5所示。以屏幕左
图3-5 n 度盒分形生成示意图
上角作为坐标原点,x 轴水平向右为正,y 轴垂直向下
为正,递归函数printBox(k,x,y)生成以坐标(x,y)为
左上角的k 度盒分形。递归生成符号为X 的n 度盒
分形可表述如下。
(1)n =1 时,到达递归边界,在(x,y)输出符
号X。
(2)n>1时,需要分别在左上、右上、中间、左下和
右下生成5个n-1盒分形,n-1度盒分形对应正方
形的边长为m =3n-2。
① 左上方n-1度盒分形,其左上角的坐标为(x, 
y),调用printBox(n-1,x,y)函数生成。
② 右上方n-1度盒分形,其左上角的坐标为(x+2m ,y),调用printBox(n-1,x+ 
2m,y)函数生成。
③ 居中的n-1度盒分形,其左上角的坐标为(x+m ,y+m ),调用printBox(n-1, 
x+m,y+m)函数生成。
④ 左下方n-1度盒分形,其左上角的坐标为(x,y+2m ),调用printBox(n-1,x, 
y+2m)函数生成。
⑤ 右下方n-1度盒分形,坐标为(x+2m ,y+2m ),调用printBox(n-1,x+2m, 
y+2m)函数生成。
3.4.2 盒分形代码分析
本节的盒分形算法代码将分形信息保存于二维数组map[][]中。当某个位置存在分
形标志时,map[i][j]的值用符号'X'表示,否则用空格表示。分形算法主要通过递归函数
FractalBox()实现。FractalBox()函数有4个参数,maps[][MAX_DEGREE]用于保存分
形信息对应的标志,degree代表当前调用对应的分形度数,x和y代表分形对应的坐标
位置。为
了简化输出盒分形的复杂度,将盒分形信息保存于二维字符数组map[][]中,处理
结束后以字符串的形式输出。主函数执行时,①计算n 度分形对应的边长3n-1;②初始
化保存分形信息的数组map[]各元素为单个空格,将行尾置为'\0';③调用FractalBox()

56 
函数以递归方式求解分形信息;④以字符串方式输出分形信息。实现代码如下。 
#include <iostream> 
#include <cmath> 
using namespace std; 
const int MAX_DEGREE = 730; //最大规模为7 度盒分形:n=3^(7-1)=3^6=729 
void FractalBox(char maps[][MAX_DEGREE], int degree, int x, int y) 
{ 
//度为1 时到达递归边界 
if (degree == 1) 
maps[x][y] = 'X'; 
else 
{ 
//n-1 度盒分形的规模m=3^(n-2) 
int m = pow(3.0, degree - 2); 
//x 为行坐标,y 为列坐标 
//左上方的n-1 度盒分形 
FractalBox(maps, degree - 1, x, y); 
//右上方的n-1 度盒分形:行未变,列增大 
FractalBox(maps, degree - 1, x, y + 2 * m); 
//中间的n-1 度盒分形:行列均增大 
FractalBox(maps, degree - 1, x + m, y + m); 
//左下方的n-1 度盒分形:行增大,列不变 
FractalBox(maps, degree - 1, x + 2 * m, y); 
//右下方的n-1 度盒分形 
FractalBox(maps, degree - 1, x + 2 * m, y + 2 * m); 
} 
}i
nt main() 
{ 
char maps[MAX_DEGREE][MAX_DEGREE]; 
int n; 
cin >> n; 
int degree = pow(3.0, n - 1); 
//初始化 
for (int i = 0; i < degree; i++) { 
for (int j = 0; j < degree; j++) { 
maps[i][j] = ' '; 
maps[i][degree] = '\0'; 
} 
} 
FractalBox(maps, n, 0, 0); 
//输出 
for (int i = 0; i < degree; i++) 
cout << maps[i] << endl;

57 
return 0; 
}
测试数据及运行结果如下。
当输入度数为3时,盒分形运行结果如下。