一个函数调用了它自己,称为递归。递归和循环可以互相替代。一种程序设计语言,支持
递归就可以不需要支持循环,支持循环就可以不需要支持递归。例如,早期的Lisp语言,就不
支持循环,只支持递归。当然,为了方便使用,程序设计语言一般都既支持递归,也支持循环。
下面这个循环调用了n次doSomething函数:
for(int i=0;i<n;++i)
doSomething();
可以用对递归函数的调用来替代:
void loop(int n)
{
if (n ==0)
return;
doSomething();
loop(n-1);
}l
oop(8); //调用8 次doSomething()函数
从替代循环的角度来看,递归和循环一样是一种手段,可以用来解决任何问题。但是递归
更多的是一种解决问题的思想———从这个角度看,也可以称递归是一种算法。
求整型数组a的最大值,可以按如下方法来实现:
int maxValue(int [] a)
{
int ans =a[0];
for (int i=1;i<a.length;++i)
if( ans <a[i])
ans =a[i];
return ans;
}
也可以用递归的思想来实现。思路是:如果a的长度是1,则最大值就是a[0];否则,最
大值就是a[1]到a[a.length-1]中的最大值以及a[0]这两者中较大的那个。递归程序如下:
int maxValue (int [] a,int start)
{ //求从a[start]开始往后的所有元素中的最大值
50
if( start ==a.length-1)
return a[start];
return Math.max(a[start], maxValue(a,start+1));
}
调用该函数的代码如下:
int a[] ={1111,2,43,23,332,11222};
int m =maxValue(a,0);
该递归函数与循环的写法相比没有什么优势,但其体现的问题分解的思路是特别有用的,
即把规模大的问题不断分解为规模小的问题,最终加以解决。要求a的最大值,可以先解决一
个形式相同但规模更小的子问题,即a[1]到a[a.length-1]中的最大值(因a[1]到a[a.length-1]
可以看作一个比a更短的数组)。这个子问题解决了,将其答案和a[0]做个比较,即可得到原
问题的答案。
本章主要通过具体例题,分以下3种情况讲述递归的用途:
(1)替代多重循环来进行枚举。
(2)解决用递归形式定义的问题。
(3)将问题分解为规模更小的子问题进行求解。
上述3种情况其实没有、也不需要有严格的区分界限。有的问题,归类为上述不止一种情
况都说得过去。例如5.2节的例题“绘制雪花曲线”,归类为第(2)、第(3)种情况都可以。
第(3)种情况,如果分解出来的子问题不止一个且相互无重叠,一般来说就可以算是“分
治”。
还有一种递归可以称之为“间接递归”,例如函数A 调用了函数B,函数B调用了函数C,
函数C又调用了函数A,就可以说函数A、B、C 都间接递归调用了自身。本章不涉及这类
递归。
5.1 用递归进行枚举
有一类问题,本质上可以归结为:有n 个变量,每个变量可以有m 种取值。这n 个变量
取值的某些组合,能够满足某个条件,求出所有满足条件的组合。本章习题中的“奥数问题”
“棋盘问题”,接下来要讲的案例“N 皇后问题”和“全排列”,本质都是如此。
这类问题最简单的解法就是暴力枚举所有组合,对每个组合检验其是否满足条件。这样
一共要枚举mn 种组合,可以用n 重循环来解决。当n 大的时候,多重循环不好写,因此可以
用递归的写法进行枚举。
5.1.1 案例:N 皇后问题(P0230)
将N 个皇后摆放在一个N 行N 列的国际象棋棋盘上,要求任何两个皇后不能互相攻击
(两个皇后在同一行,或同一列,或某个正方形的对角线上,就会互相攻击,称为冲突)。输入皇
后数N(1≤N≤9),输出所有的摆法。无解输出“NO ANSWER”。行列号都从0开始算。
输入:一个整数N,表示要把N 个皇后摆放在一个N 行N 列的国际象棋棋盘上。
输出:所有的摆放方案。每个方案一行,依次是第0行皇后位置、第1行皇后位置、……、
第N-1行皇后位置。多种方案输出顺序如下:优先输出第0行皇后列号小的方案。如果两
51
个方案第0行皇后列号一致,那么优先输出第1行皇后列号小的方案,以此类推。
样例输入
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();
52
43. new NQueensProblem(n).solve();
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 案例:全排列(P0240)
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有排列。假设对于小写
字母有a' '<b' '<…<y' '<z' ',而且给定的字符串中的字母已经按照从小到大的顺序排列。
53
输入:输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度为
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("");
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. }
54
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的阶乘是
什么”,就要回答“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)
55
所以函数的复杂度是O(n)。
5.2.1 案例:波兰表达式(P0250)
波兰表达式是一种把运算符前置的算术表达式。例如,一般形式的表达式2+3的波兰
表示法为+23。波兰表达式的优点是计算时不需要考虑运算符的优先级,因此不必用括号
改变运算次序,例如,(2+3)*4的波兰表示式为* +234。本题求解波兰表达式的值,其
中运算符包括+、-、*、/四个。
输入:输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出:输出为一行,为表达式的值。
样例输入
* +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]处开始取出若干元素构成一个波兰表达式并返回其值
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. }
56
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°,正北方
向是270°。当然也可以说正北方向是-90°,正西方向是-180°。
绘制雪花曲线须在窗口上进行。雪花曲线也称为科赫曲线,其递归定义如下。
(1)长为size,方向为x(单位:弧度)的0阶雪花曲线,是沿方向x 绘制的一根长为size
的线段。
(2)长为size,方向为x 的n 阶雪花曲线,由以下4部分依次拼接组成。
1.长为size/3,方向为x 的n-1阶雪花曲线。
2.长为size/3,方向为x-π/3的n-1阶雪花曲线。
3.长为size/3,方向为x+π/3的n-1阶雪花曲线。
4.长为size/3,方向为x 的n-1阶雪花曲线。
图5.1~图5.3是几个雪花曲线的示意图。
绘制长度为600px,方向为0的3阶雪花曲线的程序如下。
//prg0380.java
1. import javax.swing.*; //图形界面需要
2. import java.awt.*; //画图需要
3. class SnowCurveWindow extends JFrame {
57
图5.1 0阶和1阶雪花曲线
图5.2 2阶雪花曲线
图5.3 3阶雪花曲线
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]);
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 的方法,设置窗体大小为800*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 {
58
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 阶雪花曲线,应
该由4段长为size/3的n-1阶雪花曲线连接而成。这个循环就依次画出这四段。若n 阶雪
花曲线的方向是dir(单位:弧度),则这4段的方向依次是x,x-π/3,x+π/3,x。每一段的
终点就是下一段的起点。
5.3 用递归进行问题分解
递归解决问题的一种特别常用的基本思路是:要解决某一问题,可以先做一步,做完一步
以后,剩下的问题也许就会变成和原问题形式相同,但规模更小的子问题,那就可以递归求解
了。第一步如果有多种选择,则要枚举第一步的所有选择。当然,还需要归纳出不需要递归就
能直接解决的边界条件。
5.3.1 案例:上台阶(P0260)
有n 级台阶(0<n<20),从最下面开始走,最终要走到所有台阶上面,每步可以走一级或
两级,问有多少种不同的走法?