一个函数调用了它自己,称为递归。递归和循环可以互相替代。一种程序设计语言,支持
递归就可以不需要支持循环,支持循环就可以不需要支持递归。例如,早期的Lisp语言,就不
支持循环,只支持递归。当然,为了方便使用,程序设计语言一般都既支持递归,也支持循环。
从替代循环的角度看,递归和循环一样是一种手段,可以用来解决任何问题。但是递归更
多的是一种解决问题的思想———从这个角度看,也可以称递归是一种算法。
本章主要通过具体例题,分为以下三种情况讲述递归的用途。
(1)替代多重循环来进行枚举。
(2)解决用递归形式定义的问题。
(3)将问题分解为规模更小的子问题进行求解。
上述三个方面其实没有也不需要有严格的区分界限。有的问题,归类为上述不止一种情
况都说得过去。例如,5.2节的例题“绘制雪花曲线”,归类为第(2)或第(3)种情况都可以。
第(3)种情况,如果分解出来的子问题不止一个且相互无重叠,一般来说就可以算是“分治”。
还有一种递归可以称为“间接递归”,例如,函数A 调用了函数B,函数B 调用了函数C, 
函数C 又调用了函数A ,就可以说函数A 、B、C 都间接递归调用了自身。本章不涉及这类
递归。
5.1　用递归进行枚举
5.1.1 案例: N 皇后问题(P0230) 
将N 个皇后摆放在一个N 行N 列的国际象棋棋盘上,要求任何两个皇后不能互相攻击
(两个皇后在同一行,或同一列,或某个正方形的对角线上,就会互相攻击,称为冲突)。输入皇
后数N (1≤N ≤9),输出所有的摆法。无解输出“NOANSWER”。行列号都从0开始算。
输入:一个整数N ,表示要把N 个皇后摆放在一个N 行N 列的国际象棋棋盘上。
输出:所有的摆放放案。每个方案一行,依次是第0行皇后位置、第1行皇后位置、……、
第N -1行皇后位置。多种方案输出顺序如下:优先输出第0行皇后列号小的方案。如果两
个方案第0行皇后列号一致,那么优先输出第1行皇后列号小的方案,以此类推。

60 
样例输入 
4
样例输出 
1 3 0 2 
2 0 3 1 
解题思路:在皇后数目不确定的情况下,用循环解决比较麻烦,因此可以采用递归的方式
进行枚举,程序如下。 
//prg0350.java 
1. import java.util.*; 
2. class NQueensProblem { 
3. int N; 
4. int [] result; //result[i]是第i 行皇后摆放位置
5. NQueensProblem(int n_) { 
6. N = n_; result = new int[N]; 
7. } 
8. boolean isOk(int n,int pos) { //判断第n 行的皇后放在第pos 列是否可行
9. //此时第0 行到第n-1 行的皇后的摆放位置已经存放在result[0]至result[n-1]中
10. for (int i = 0;i < n; ++i) 
11. //检查位置pos 是否会和前0~n-1 行已经摆好的皇后冲突
12. if (result[i] == pos || 
13. Math.abs(i-n) == Math.abs(result[i] - pos)) 
14. return false; 
15. return true; 
16. } 
17. boolean queen(int i) { 
18. //解决N 皇后问题,现在第0 行到第i-1 行的i 个皇后已经摆放好了
19. //要摆放第i 行的皇后。返回值表示这种情况下最终能否成功
20. if (i == N) { //已经摆好了N 个皇后,说明问题已经解决,输出结果即可
21. for (int k=0;k<N;++k) 
22. System.out.print(result[k]+" "); 
23. System.out.println(); 
24. return true; 
25. } 
26. boolean succeed = false; 
27. for (int k=0;k<N;++k) //枚举所有位置
28. if (isOk(i,k)) { //看可否将第i 行皇后摆在第k 列
29. result[i] = k; //可以摆在第k 列,就摆上
30. succeed = queen(i+1) || succeed; //接着去摆放第i+1 行的皇后
31. } 
32. return succeed; 
33. } 
34. void solve() { 
35. if (!queen(0)) 
36. System.out.println("NO ANSWER"); 
37. } 
38. } 
39. public class prg0350 { //请注意:在OpenJudge 提交时类名要改成Main 
40. public static void main(String[] args){ 
41. Scanner reader = new Scanner(System.in); 
42. int n = reader.nextInt(); 
43. new NQueensProblem(n).solve();

61 
44. } 
45. } 
queen函数返回值为true或者false,queen(i)的返回值表示:当前,前i 个皇后已经摆好
且不冲突,它们的摆法放在result[0,i-1]中(本书中用a[x,y]表示数组或字符串a 中从
a[x]到a[y]这样连续的一段),在不改变这前i 个皇后的摆法的前提下,继续往下摆放,最终
能否找到至少一种成功的N 皇后摆法。在第27行,函数试图为第i 行的皇后找到所有和前i 
个皇后不冲突的位置,所谓“枚举”,就体现在本行。每找到一个合适的位置,就摆放之,然后递
归调用一次queen(i+1)继续后面皇后的摆放;如果一个合适位置都找不到,则返回false,表
示在当前情况下,最终无法摆放成功。
第24行:由于函数是递归调用的,所以有几个解,本行就会被执行几次。例如,在第0行
皇后摆在第0列的情况下,执行queen(1)最终会成功,本行会得到执行;在第0行皇后摆放在
第1列的情况下,执行queen(1)最终也会成功,本行又会得到执行。实际上,如果有k 个解的
第0行皇后都是摆放在第0列的,则会有k 次执行到本行时,第0行皇后是摆放在第0列的。
第26行:succeed表示在当前情况下,再往下摆能否至少找到一个解,先假定为false。
第29行:假设找到的第一个合法摆放位置是k1,第i 行皇后摆放在第k1 列的情况下,会
继续执行queen(i+1),从此处一直递归下去,有可能会找到多种N 皇后的最终合法摆放方
案,即多次走到第21行,输出多个解。这些解的第0行到第i 行的摆放方案都是相同的,例
如,第i 行都是摆放在k1 位置。queen(i+1)执行过程中经历层层多分支递归,终究会返回, 
返回后回到第27行的for循环,继续寻找下一个可行的第i 行摆放位置k2,然后再继续递归
下去。因
此上面的程序会输出所有的解。
第30行:在第27 行开始的循环中,只要有一次执行本行时queen(i+1)返回true, 
succeed的值就会是true,意味着在当前情况下最终能够摆放成功。
本程序中,result数组中的一个元素,本质上就相当于多重循环解法里的一个循环控制变
量,它们都是表示一行皇后的位置的。
请注意:如果要将程序改写成找到一个解就结束,则只需要将第30行替换为下面两行。 
//prg0351.java 
if(queen(i+1)) //接着去摆放第i+1 行的皇后 
return true; 
这样的话,摆放第i 行皇后的时候,一旦发现一个能导致最终摆放成功的摆法,就不会去
尝试第i 行的下一个摆法,因此对每行的皇后,都只找到一个能导致最终成功的摆法,于是程
序的第24行只会执行1次,程序只输出一个解。
N 皇后问题的本质,是有N 个变量,这N 个变量取值的某些组合,能够满足某个条件,要
求出这些满足条件的组合。下面的奥数问题、接下来的全排列问题、习题中的棋盘问题本质都
是如此,都可以用类似N 皇后问题的办法解决。
5.1.2 案例: 奥数问题(P0100)的递归解法
本题就是4.1.2节案例“奥数问题”。这个问题和N 皇后问题很像。可以将每个字母看作
一个位置,等式中最多出现5个不同字母,所以一共有5个位置。在每个位置需要摆一个数, 
且每个位置上的数不一样。将等式中的字母用其对应位置上的数替换,要使得替换后的等式

62 
成立,且等式中不可以有带多余前导0的数出现。下面的递归程序中,这5个位置就是数组a 
的5个元素,函数done(i)表示a[0,i-1]这i 个位置已经摆上数的情况下,接着要在位置
a[i]及后面的位置摆数,求最终能否成功。 
//prg0312.java 
1. import java.util.*; 
2. class AoshuProblem2 { 
3. String s1,s2,s3; 
4. AoshuProblem2(String str1,String str2,String str3) { 
5. s1 = str1; s2 = str2; s3 = str3; 
6. } 
7. int a[] = new int[5]; //a[0]存放'A'表示的数,a[1]存放'B'表示的数…… 
8. int toInt(String s) { 
9. //依据a 将'ABE'这样的字符串转成整数。若有前导0 则返回-1 表示失败
10. String result = ""; 
11. for(int i=0;i<s.length();++i) { 
12. char c = s.charAt(i); 
13. result += (char)('0' + a[c-'A']); 
14. } 
15. if (result.length() > 1 && result.charAt(0) == '0') 
16. return -1; 
17. return Integer.parseInt(result); 
18. } 
19. private boolean done(int i) { //被调用时,a[0,i-1]已存放了i 个字母代表的数
20. //返回值表示在此情况下最终能否找到解
21. if (i == 5) { 
22. int n1 = toInt(s1),n2 = toInt(s2), 
23. n3 = toInt(s3); 
24. if (n1 >= 0 && n2 >= 0 && n3 >= 0 
25. && n1 + n2 == n3) { 
26. System.out.printf("%d+%d=%d\n",n1,n2,n3); 
27. return true; 
28. } 
29. } 
30. else { //i!= 5 
31. for(int k=0;k<10;++k) { 
32. int j = 0; 
33. for(;j<i;++j) //本循环判断k 这个数是否已经被用过
34. if(a[j] == k) 
35. break; //发现k 这个数已经被用过
36. if(j == i) { //如果k 这个数还没被用过
37. a[i] = k; //在位置i 摆数k,即让第i 个字母代表数k 
38. if (done(i+1)) 
39. return true; 
40. } 
41. } 
42. } 
43. return false; 
44. } 
45. void solve() { 
46. if (!done(0)) 
47. System.out.println("No Solution"); 
48. } 
49. }

63 
50. public class prg0312 { //请注意:在OpenJudge 提交时类名要改成Main 
51. public static void main(String[] args){ 
52. Scanner reader = new Scanner(System.in); 
53. int n = reader.nextInt(); 
54. for(int i=0;i<n;++i) { 
55. String s1 = reader.next(),s2 = reader.next(), 
56. s3 = reader.next(); 
57. new AoshuProblem2(s1,s2,s3).solve(); 
58. } 
59. } 
60. } 
本程序在位置i 摆放数k 前,先判断能不能摆,能摆了才摆,而不是不管能不能摆,把5个
位置都摆上数再判断整个完整的摆法是否符合要求,这样可以提高效率。
5.1.3 案例: 全排列(P0240) 
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有排列。假设对于小写
字母有a' '<b' '<…<y' '<z' ',而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入:输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度为
1~6。输
出:输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前
面。字母序如下定义。
已知S=s1s2…sk ,T =t1t2…tk ,则S<T 等价于,存在p(1≤p≤k),使得s1=t1,s2= 
t2,…,sp-1=tp-1,sp <tp 成立。
样例输入 
abc 
样例输出 
abc 
acb 
bac 
bca 
cab 
cba 
本题的本质就是在n 个位置(编号0~n-1)摆n 个不同字母,要求给出符合“每个字母只
出现一次”这个要求的所有摆法。解题程序如下。 
//prg0360.java 
1. import java.util.*; 
2. class AllPermutations { 
3. String lst; //存放输入的字符串
4. char [] result; //result[i]表示第i 个位置摆放的字母
5. boolean [] used; //used[i]表示lst 中的第i 个字母是否已经用过
6. int n; //排列的长度是n 个字符
7. void permutation(int i) { //从第i 个位置起摆放字母
8. if (i == n) { //条件满足则说明n 个位置都摆上字母了,即发现了一个排列
9. for (char x:result) 
10. System.out.print(x); 
11. System.out.println("");

64 
12. return; 
13. } 
14. for (int k=0;k<n;++k) 
15. if (!used[k]) { //第k 个字母还没用过
16. result[i] = lst.charAt(k); //在第i 个位置摆上第k 个字母
17. used[k] = true; 
18. permutation(i+1); //从第i+1 个位置起继续往下摆
19. used[k] = false; 
20. } 
21. } 
22. void solve() { 
23. Scanner reader = new Scanner(System.in); 
24. lst = reader.next(); 
25. n = lst.length(); 
26. result = new char [n]; 
27. used = new boolean[n]; 
28. for (int i=0;i<n;++i) 
29. used[i] = false; 
30. permutation(0); //从第0 个位置开始摆放字母
31. } 
32. } 
33. public class prg0360 { //请注意:在OpenJudge 提交时类名要改成Main 
34. public static void main(String[] args){ 
35. new AllPermutations().solve(); 
36. } 
37. } 
函数permutation(i)表示,在0~i-1这i 个位置已经摆好字母的情况下,从第i 个位置
开始继续摆放字母。位置k 摆放的字母,记录在result[k]中(k=0,1,…,n-1)。
第14行:枚举所有在第i 个位置可能摆放的字母,k 是字母在lst中的下标。由于在每个
位置枚举字母的时候都是按照字母从小到大的顺序进行,所以最终会按从小到大的顺序得到
一个个排列,类似于N 皇后问题得到解的顺序。
第15行:一个排列中,每个字母只能用一次,因此用数组元素used[k]记录字母lst[k]是
否已经被用过。lst[k]还没用过,就可以摆在位置i。摆上后就要将used[k]设置为true,表示
lst[k]已经被使用,如第17行所示。
第19行:下次循环就要在位置i 尝试摆放别的字母。要在位置i 摆别的字母,就应该将
刚才在第16行摆放在位置i 的字母lst[k]拿走,那么字母lst[k]就应该恢复成没用过,这样
在后续位置还可以摆放它。因此要让used[k]=false。
5.2　解决用递归形式定义的问题 
有一些问题或者概念,本身的定义就是递归形式的。例如“自然数n 的阶乘”这个概念, 
可以定义成1×2×3×…×(n-1)×n,也可以用以下两句话来定义。
(1)1的阶乘是1。
(2)n>1时,n 的阶乘等于n 乘以(n-1)的阶乘。
第(2)句话,定义“阶乘”这个概念的时候,用到了“阶乘”这个词,看上去像循环定义,让人
无法理解。但是,由于有语句(1)的存在,上面这两句“自然数n 的阶乘”的定义,就是严密且
可以理解的。例如,若问“3的阶乘是什么”,要先回答“2的阶乘是什么”;要回答“2的阶乘是

65 
什么”,就要回答“1的阶乘是什么”。按照语句(1),1的阶乘是1,因此往回倒推就可以知道3 
的阶乘是什么了。
可以说,在上面的两句话的阶乘定义中,语句(2)的形式是递归的,而语句(1)就是递归的
终止条件。
按照这种定义方式,求自然数n 的阶乘的函数可以写成: 
int factorial(int n) { 
if (n == 1) 
return 1; 
return n * factorial(n-1); 
}
这是最简单的用递归函数解决递归形式的问题的例子。
在上面的程序中,判断“n==1”是否为真是基本操作,即进行次数最多的操作。设求n 
阶乘的基本操作次数为T(n),则有: 
T(n)=1+T(n-1)=1+1+T(n-2)=1+1+1+T(n-3)=… 
=1+1+…+T(1)=1+1+…+1(n 个1) 
所以函数的复杂度是O(n)。
5.2.1 案例: 波兰表达式(P0250) 
波兰表达式是一种把运算符前置的算术表达式。例如,一般形式的表达式2+3的波兰
表示法为+23。波兰表达式的优点是计算时不需要考虑运算符的优先级,因此不必用括号
改变运算次序,例如,(2+3)*4的波兰表示式为* +234。本题求解波兰表达式的值,其
中运算符包括+、-、*、/4个。
输入:输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出:输出为一行,表达式的值。
样例输入 
* + 11.0 12.0 + 24.0 35.0 
样例输出 
1357.000000 
虽然什么是“波兰表达式”不难理解,但是题目其实并没有给出“波兰表达式”的准确定义。
波兰表达式可以用递归的形式准确定义如下。
(1)一个数是一个波兰表达式,其值就是该数本身。
(2)若一个波兰表达式不是一个数,则其形式为:“运算符波兰表达式1波兰表达式2”, 
其值是以“波兰表达式1”的值作为第一操作数,以“波兰表达式2”的值作为第二操作数,进行
“运算符”所代表的运算后的值。“运算符”有加减乘除4种,分别表示为“+”“-”“*”“/”。
根据上述定义,可以写出解题程序如下。 
//prg0370.java 
1. import java.util.*; 
2. class PolishExpression { 
3. int N; 
4. String [] exp; //exp[i]要么是一个数的字符串形式如"11.0",要么是一个运算符
5. double polish() { //从exp[N]处开始取出若干元素构成一个波兰表达式并返回其值

66 
6. int M = N; 
7. ++ N; 
8. if (exp[M].equals("+")) 
9. return polish() + polish(); 
10. else if (exp[M].equals("-")) 
11. return polish() - polish(); 
12. else if (exp[M].equals( "*")) 
13. return polish() * polish(); 
14. else if (exp[M].equals( "/")) 
15. return polish() / polish(); 
16. else 
17. return Double.parseDouble(exp[M]); 
18. } 
19. void solve() { 
20. Scanner reader = new Scanner(System.in); 
21. exp = reader.nextLine().split(" "); 
22. N = 0; 
23. System.out.printf("%.6f\n",polish()); 
24. } 
25. } 
26. public class prg0370 { //请注意:在OpenJudge 提交时类名要改成Main 
27. public static void main(String [] args) { 
28. new PolishExpression().solve(); 
29. } 
30. } 
第3行:N 相当于一个指针,表示polish函数被调用时,应该从字符串数组exp中下标为
N 的元素开始,取出若干个元素(假设x 个)构成一个波兰表达式,计算出其值并返回。而且
polish函数还必须让N 变为N +x,以便下一次调用polish函数时可以从正确的位置继续取
元素。例如,N ==0时调用polish(),一定是将exp中的所有元素都取出作为一个波兰表
达式。第
8、9行:按照波兰表达式定义,如果exp[M ]是“+”,则其后面一定跟着两个波兰表达
式。“+”取走后,N 的值被加1。然后调用一次polish()取出第一个波兰表达式并算出值,且
让N 推进到合适位置,再调用一次polish()取出第二个波兰表达式,算出值,和第一个波兰表
达式的值相加后返回。当然,第二次调用polish()的时候也会推进N 到合适位置。
第17行:按照波兰表达式定义,如果exp[M ]不是运算符,则其一定是一个数。那么取出
的波兰表达式就是exp[M ],其值为exp[M ]代表的那个数。
由于只需要从头到尾扫描整个表达式一遍,所以复杂度为O(n)。
★★5.2.2 案例: 绘制雪花曲线
绘制雪花曲线,更是典型的以递归形式定义的问题。
要进行绘图,需要导入javax.swing包和java.awt包。前者中的JFrame类用于生成一个
窗口,后者中的Graphics类用于画图。Graphics对象可以看作窗口上的画板,调用Graphics 
对象的drawLine()方法,可以绘制线段。
绘图是在一个窗口中进行的,创建了一个JFrame对象,就创建了一个窗口。JFrame对
象的setSize()方法可以设置窗口大小。窗口是一个平面直角坐标系,窗口的左上角是坐标系
原点,即其坐标是(0,0)。规定正东方向是0°,正南方向是90°,正西方向是180°,正北方向是

67 
270°。当然也可以说正北方向是-90°,正西方向是-180°。
绘制雪花曲线须在窗口上进行。雪花曲线也称为科赫曲线,其递归定义如下。
(1)长为size,方向为x(单位:弧度)的0阶雪花曲线,是沿方向x 绘制的一根长为size 
的线段。
(2)长为size,方向为x 的n 阶雪花曲线,由以下4部分依次拼接组成。
① 长为size/3,方向为x 的n-1阶雪花曲线。
② 长为size/3,方向为x-π/3的n-1阶雪花曲线。
③ 长为size/3,方向为x+π/3的n-1阶雪花曲线。
④ 长为size/3,方向为x 的n-1阶雪花曲线。
图5.1~图5.3是几个雪花曲线的示意图。
图5.1 0阶和1阶雪花曲线
图5.2 2阶雪花曲线
图5.3 3阶雪花曲线
绘制长度为600像素,方向为0的3阶雪花曲线的程序如下。 
//prg0380.java 
1. import javax.swing.*; //图形界面需要
2. import java.awt.*; //画图需要
3. class SnowCurveWindow extends JFrame { 
4. public void drawSnowCurve(Graphics g, int n,int x,int y, 
5. double size,double dir) { 
6. //在g 上绘制一个n 阶长度为size,方向为dir(单位:弧度)的雪花曲线,起点坐标为(x,y) 
7. if(n == 0) { //下面画一条0 阶雪花曲线,即一个线段
8. int x2 = (int)Math.round(x + Math.cos(dir)*size); 
9. int y2 = (int)Math.round(y + Math.sin(dir)*size); 
10. g.drawLine(x,y,x2,y2); //从起点(x,y)到终点(x2,y2)画一条线段
11. } 
12. else { 
13. double delta[] = {0,-Math.PI/3,Math.PI/3,0}; //PI 是π 
14. size /= 3; 
15. for(int i=0;i<4;++i) { 
16. drawSnowCurve(g,n-1,x,y,size,dir+delta[i]);

68 
17. x = (int) Math.round((x + Math.cos(dir+delta[i])*size)); 
18. y = (int) Math.round((y + Math.sin(dir+delta[i])*size)); 
19. } 
20. } 
21. } 
22. public SnowCurveWindow(int n,int x,int y, 
23. int size,double dir){ 
24. setSize(800,600); //JFrame 的方法,设置窗体大小为800px*600px 
25. setLocationRelativeTo(null); //让窗口在屏幕上居中
26. setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
27. setContentPane(new JPanel() { 
28. public void paint(Graphics g){ 
29. drawSnowCurve(g,n,x,y,size,dir); 
30. } 
31. }); 
32. setVisible(true); 
33. } 
34. } 
35. public class prg0380 { 
36. public static void main(String[] args) { 
37. new SnowCurveWindow (3,100,400,600,0); 
38. //绘制3 阶长度为600,方向为0 的雪花曲线,起点坐标为(100,400) 
39. } 
40. } 
程序运行结果如图5.4所示。
图5.4 3阶0°雪花曲线
类SnowCurveWindow从JFrame派生而来,第37行创建一个SnowCurveWindow对象, 
即创建了一个窗口。SnowCurveWindow 构造方法中调用的各种以“set”开头的方法,都是
JFrame类的方法。
第27行:本行new出来的对象,是一个匿名类的对象,该匿名类从JPanel类派生而来并
重写了paint()方法。JPanel对象可以看作一个面板,可以在上面绘图。setContentPane在窗
口上放置该匿名类对象,窗口显示和刷新时,会调用该匿名类对象的paint()方法并传入画布
对象Graphicsg。因此要将绘制雪花曲线的代码,即对drawSnowCurve函数的调用,写在
paint()方法中。
第13~19行:按照雪花曲线的递归定义,一条dir方向上的长为size的n 阶雪花曲线,应