计算机递归算法详解

递归

冯文科

一、递归的基本概念。

一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引

用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须

用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计

中，函数直接或间接调用自己，就被称为递归调用。

二、递归的最简单应用：通过各项关系及初值求数列的某一项。

在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，

于是人们想出另一种办法来描述这种数列：通过初值及明与前面临近几项之间的关系。

要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各

项的关系。

比如阶乘数列

1、2、6、24、120、720......

如果用上面的方式来描述它，应该是：

=1

an=1।

na„_},n>1

如果需要写一个函数来求3的值，那么可以很容易地写成这样：

intf(intn)

(

if(n==l)

return1;

returnn*f(n-1);

)

这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一

些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二

个出口。

递归函数的执行过程总是先通过递归关系不断地缩小问题的规模,直到简单到可以作为

特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问

题的解。

以上面求阶乘数列的函数/(〃)为例。如在求/(3)时，由于3不是特殊值，因此需要计

算3*/(2),但/(2)是对它自己的调用，于是再计算/(2),2也不是特殊值，需要计算

需要知道/.⑴的值，再计算/⑴，1是特殊值，于是直接得出"1)=1，返回上

1

-步，得/(2)=2*/(1)=2,再返回上一步，得/(3)=3*/(2)=3*2=6,从而得最

终解。

用图解来说明，就是

/(3)的执行过程/(2)的执行过程/⑴的执行过程

(特殊值判断：)(特殊值判断：)(特殊值判断：)

3x1,继续向下。2x1,继续向下。1=1,由特殊情

(递归关系处理：)(递归关系处理：)况出口直接返回lo

求3*/(2),需要先求2*/(1),需要先

计算/(2),调用计算/⑴，调用

且本身挂起且本身挂起

得至1」/(2)=2,由正得到/⑴=1,由正

常出口返回3*2常出

下面再看一个稍复杂点的例子。

【例1】数列｛明｝的前几项为

11I

、、

1+-------

1+1

输入〃，编程求明的精确分数解。

分析：

这个题目较易，发现4=1,其它情况下有%=---。如要求实数解的话，这基本

1+

已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设%।=2,

P

则由递归关系，有*=—1—=—，再约分化简，即得明。但发现一个问题:

1+Q11qp+q

P

2

求出心T时，需要返回两个整数：分子夕与分母夕,而通常的函数只能返回一个整数。

这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返

回两个变量了（其实还可以不只两个呢）；另•种是在求值函数的参数表中加入两个指针变

量或引用变量，通过参数给带回数值。但由于后一种做法会使程序结构不清晰——返回值是

由参数表得到的，因此我们使用前一种方法。

另外，在通过心।=且得出%=上一后，a“就已经是最简分数了，无须化简。证明

pp+q

如下：

若4是最简分数，即说明P,夕的最大公约数为1,即对任何Iv厂Wq,都有qmod〃与

P

P1110（3/,不全为0,不防记gmod尸=a、pmodr=h9则有

（p+q）modr=（a+b）modr

只要a与b不全为0,且。<r,b<rf就有a与（a+b）modr不全为0。因此对任何的

\<r<q,有pmodr与（p+q）modr不全为0。

而对于q<r<p的情况而言，记pmodr=a,则有

（p+q）mod/=（a+q）modr

由于0Kavr,0<q<r,因此同样有pmod/与（p+（7）modr不全为0。

所以对任意1<rWp,都有pmod/与（P+4）modr不全为0,因此它们的最大公约

数为1,即一“一是最简分数。虽然这是个要求4一（即反）是最简分数的结论，但由于数

。+夕P

列第二项为,，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的a“，

2

求出的一^就是最简分数，无须化简。

p+q

具体代码如下：

//Examl.cpp

♦include<iostream>

usingnamespacestd;

structFS

3

unsignedlonglongq,p;

)；

FSf(intn)

(

FSr;

if(n==l)

(

r.q=l;

r.p=l;

returnr;

)

r=f(n-1);

r.p=r.p+r.q;

r•q=r.p-r.q;

returnr;

)

intmain()

(

FSr;

intn;

cin»n;

r=f(n);

cout«r.q«1/*<<r.p«endl;

system(HpauseH);

return0;

三、递归的精髓：只考虑当前•步，剩下的让下•步去做吧。

对大多数问题而言，当它的规模缩小至“特殊情况”时，都可以非常轻易地得出问题的

解，因此我们不过多地讨论“特殊情况”，只详细地讨论递归关系的确定。

寻找递归关系，最低标准是它能使问题的规模变小，且变小后的问题与原问题在本质h

是一样的。当找到递归关系后，我们的递归函数只须处理特殊情况与递归关系，不需要处理

其它的信息——至于下一步的事情，就让下一步去做吧。

另一个需要考虑的事情就是递归函数的参数表，首先，在通常情况下，参数表都要使用

变量参数，且递归函数中尽量使用局部变量一一这会减少很多不必要的麻烦；其次，参数表

中，大多都有一个表示当前在执行第几步的参数。

4

【例2】下图是一个有向图，输入N(0WNW9),打印0—N的所有路径。

仔细研究这个图的特点，发现以下规律：对任何结点i,都可以走到i+1和i+2,当然

如果它们不超过9的话。由于要打印路径，因此需要保存查找过程中的部分路径信息。

可以做一个全局数组path□来存储这个信息，由于结点0没有来路，且是所有路径的起

点，因此记path[0]=0,递归函数负责填写之后的路径结点。

我们这样设计递归函数：

首先，这个递归函数的参数表中至少需要•个参数i，它的意义是表示现在在填路径中

的第几个结点，而path[i]可以填的数，要么是上一个结点加1,要么是上一个结点加2,即

path[i]=path[i-l]+l或path[i]=path[i-1]+2：

其次，特殊情况的讨论：我们要找的是终止到N的路径，因此若出现path[i-l]=N的情

况，就说明已经找到路径，无须将当前层再填入结点，可以将path中的信息输出并结束函

数了——这是递归函数的特殊情况出口；

第三、递归关系的处理：若还没到达结点N,则填写本结点path[i],上文已说明，

path[i]=path[i-l]+l或path[i]=path[i-l]+2,当然如果它们都不过9的话。将结点i填好后，说

明路径向下走了一步，距离结点N更近了一步，问题规模已经变小。不要处理其它东西，

直接递归，通过递归调用去填写i+1结点就可以了。

这里有处和【例1】不相同的地方，即path[i]是有两种可能可选的，我们的处理这这样

的，先令path[i]=path[i-l]+l,然后递归调用，填写i+1结点，当这个调用返回时，说明所有

path[i]为path[i-l]+l的路径都已经讨论完成了，再令path[i]=path[i-l]+2,再递归，当它返回

时，整个函数执行完毕，形成正常的执行完成时的出口。

具体代码如下：

//Exam2.cpp

♦include<iostream>

usingnamespacestd;

♦defineMAX9

intpath[MAX],N;

intwrite(inti)

{

intj;

for(j=0;j<i;j++)

cout<<path[j];

cout«path[i]«endl;

)

5

voidf(inti)

(

if(path[i-1]==N)

(

write(i-1);

return;

}

if(path[i-l]+l<=N)

(

path[i]=path[i-1]+1;

f(i+D；

)

if(path[i-1]+2<=N)

(

path[i]=path[i-1]+2;

f(i+1)；

)

intmain()

(

cin>>N;

path[0]=0;

f(1)；

system("pause11);

return0;

【例3】我的画笔。

Windows中的画笔从Windows3.x时代开始就12经有了，虽然功能与Photoshop不能相

比，但它小巧而迅速，一般的简单功能还是很方便的。

画笔中的填色工具是油漆桶，选定它，再指定一个颜色，在图片中一点，所有与这个点

颜色相同且相连的象素就都被填充了。如下图示：

画笔的油漆桶工具填充的是一个叫“四连通”的区域，即它只从上、下、左、右四个方

向向外扩展。

请编写程序，模拟油漆通工具。

输入文件：Exam3In.txt中有10行，每行是一个10字符的字符串，表示一个10*10的

图象，不同的字符表示不同的颜色；之后的一行有两个用空格分开的整数，表示油漆桶点中

6

的位置，再后面一行是一个字符，表示油漆桶的填充颜色。

输出文件：Exam30ut.txt,输出10行，每行10个字符的字符串，表示填充后的图象。

分析：

本题给了一个点的位置，查找所有与它“四连通”的点就成为本题的核心问题。我们的

算法是这样的：先从这个起点出发，沿四个方向展开，看这“直接相连”的四个点是否可以

填充，若有可以的，则再以这个点为中心，再向四个方向展开……直到所有可能展开的点都

不能再展开了为止。

递归函数这样设计：首先它的参数表需要两个参数，表示本次从哪个位置点展开；其次,

依次讨论它四个方向上相邻的点是否可填充——与起点颜色相同，如果可以，则填充，并以

此点为中心，递归调用。

代码如下：

//Exam3.cpp

#include<fstream>

usingnamespacestd;

#defineN10

ifstreamfin(HExam3ln.txtH;

ofstreamfont("Exam30ut.txt");

charpic[N][N+l],c,p;

intcol,row;

voidfill(inti,intj)

(

if(i-l>=0&&pic[i-1][j]==p)

(

pic[i-l][j]=c;

fill(i-1,j)；

)

if(i+l<N&&pic[i+1][j]==p)

(

pic[i+l][j]=c;

fill(i+lzj);

)

if(j-l>=0&&pic[i][j-l]==p)

(

pic[i][j-l]=c;

fill(izj-1)；

)

if(j+l<N&&pic[i][j+1]==p)

{

pic[i][j+l]=c;

7

j+D；

)

)

intmain()

(

inti;

for(i=0;i<N;i++)

fin»pic[i];

fin»row»col;

fin»c;

p=pic[row][col];

pic[row][col]=c;

fill(row,col);

for(i=0;i<N;i++)

fout<<pic[i]«endl;

return0;

本题中的递归函数fill似乎与常规的递归函数比较起来缺少了处理特殊情况的部分，其

实不然，它的特殊情况处理已经被融合到递归关系的处理当中了，正常与非正常的出口合并

到一起。特殊情况就是：当向四个方向都无法展开时，程序直接退出。

这个程序的fill函数运用的算法就是“种子填充算法”的递归写法。它另有动态规划的

写法——当然比这个要快得多，大家可以想一想如何实现。

四、递归函数的必然用法：处理递归定义的数据结构。

一些常用的数据结构本身就是递归定义的，写一个递归的函数来处理它，当然是再正常

不过的事情，就比如说二叉树、广义表……

【例4】二叉树的操作。

用字符串的形式给定一个完全二叉树，保存在输入文件Exam4In.txt中，编写程序输出

其后序遍历的结果至输出文件Exam40ut.txt中。

分析：

本题的程序是简单的，唯一要注意的是：C++的数组从下标0开始，因此对于结点i,

它的左孩子编号应该是2i+l,右孩子编号应该是2(1+1)。其它的地方没什么难度。

代码如下：

//Exam4.cpp

♦include<fstream>

usingnamespacestd;

#defineM100

8

ifstreamfin(HExam4In.txt");

ofstreamfout("Exam40ut.txtn);

chartree[M];

intL;

voidrun(inti)

(

if(2*i+l<L)

run(2*i+l);

if(2*(i+l)<L)

run(2*(i+l));

fout<<tree[i];

)

intmain()

(

fin»tree;

L=strlen(tree);

run(0);

return0;

)

【例5】以字符串形式给出一棵完全二叉树的先序遍历与中序遍历序列，编程输出用字符串

形式表示的完全二叉树的结构。

分析：

先序遍历的首结点一定是整棵树的根，因此可以直接标在0处。在中序遍历序列中，它

左边的结点构成左子树，右边的结点构成右子树，从而可以知道，左子树与右子树的结点个

数，进而得到及左子树与右子树的先序遍历与中序遍历序列，递归查找所有子树的根即可。

为了得到整棵树的结构，设置全局数组tree口来存储，全局数组s口的意义是：s[i]存储

整数表示第i层结点的起始下标。

代码如下：

//Exam5.cpp

#include<fstream>

visingnamespacestd;

#defineM100

ifstreamfin("Exam5In.txtH);

ofstreamfout("Exam50ut.txtn);

charpre[M],mid[M],tree[M];

9

intL,s[M];

voidbuild(intlayer,intps,intpe,intms,intme)

(

tree[s[layer]]=pre[ps];

s[layer]++;

if(ps==pe)

return;

inti;

i=ms;

while(mid[i]!=pre[ps])

i++；

build(layer+1,ps+1,ps+i-ms,ms,i-1);

build(layer+1^ps+i-ms+1,pezi+1,me);

)

intmain()

(

fin>>pre>>mid;

L=strlen(pre);

s[0]=0;

inti,j;

i=l；

j=2；

while(s[i]<L)

{

s[i]=j-l;

j=j*2；

i++；

)

build(0,0,L-l,0,L-l);

tree[L]='\0';

fout«tree;

return0;

)

五、递归与回溯法。

递归的另一个常用的地方是实现回溯法。

所谓回溯法，一般就是指先将问题分成几步，在每一步时尝试所有的可能，直到达到最

终要求，或最后一步将所有可能尝试完成后，再回到上一步，使上一步尝试下一种可能，并

继续的作法。由于回溯的“步骤性”明显，因此用递归实现回溯是相当方便的事。

看下面的一个例题：

10

【例6】n皇后问题。

输入整数n,打印n皇后问题的所有解及解的总数。

代码如下：

//Exam6.cpp

♦include<iostream>

usingnamespacestd;

♦defineMAX100

intn,q[MAX],c;

boolmark[MAX];

voidwrite()

(

inti;

chart[MAX];

memset(t,1.1,MAX*sizeof(char));

t[n]=,\0,;

for(i=0;i<n;i++)

(

t[q[i]]=,Q,；

cout«t<<endl;

t[q[i]]=,.

)

cout<<endl;

}

booltest(intizintk)

(

intj;

j=0;

while(j<k&&abs(j-k)!=abs(q[j]-i))

j++；

if(j==k&&mark[i]==false)

returntrue;

else

returnfalse;

)

voidsearch(intk)

(

if(k==n)

11

write();

C++；

return;

)

inti;

for(i=0;i<n;i++)

if(test(i,k))

(

mark[i]=true;

q[k]=i；

search(k+1);

mark[i]=false;

)

)

intmain()

(

cin»n;

memset(mark,0rMAX*sizeof(bool));

c=0;

search(0);

cout«c«endl;

system("pause'*);

return0;

12

六、练习

【练习】为给定的表达式建立表达式树，并求值。给定的表达式中，所有数字都是1位正整

数，出现的符号可能为+、一、*、/、(、)。

分析：

这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。

在详细说明这个算法之前，需要首先明确这个算法用到的概念

1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数；

2、项：一个项是指由*与/连接起来的若干单元；

3、表达式：一个表达式是指由十或一连接起来的若干项。

要建立表达式树，需要三个函数互相调用的函数：一个是getunit,用于建立一个单元;

一个是getexpr,用于建立一个项，另一个就是build,用于建立一个表达式。

getunit函数较易，如果字符串首字母是(的话，那么从它后面的字符开始用build建立

一个表达式，这个表达式就是一个单元；否则，就处理一个整数；

getexpr函数是建立在getunit之上的，它先用getunit建立一个单元，然后不停地考察之

后地连接符号是不是*或/,若是，则不停地重复读连接符、建立另一个单元、建立连接的操

作，直到连接符号不是*或/为止。

build函数是用于最终建立表达式的，它先用getexpr建立一个项，再用符号将剩余的各

项连接成二叉树。

代码如下：

//Exer.cpp

♦include<iostream>

usingnamespacestd;

structNODE

(

intn;

charc;

NODE*left,*right;

NODE()

(

left=NULL;

right=NULL;

)

)；

chars[100];

intcur;

NODE*tree;

voidclear(NODE*root)

13

if(root==NULL)

return;

clear(root->left);

clear(root->right);

deleteroot;

)

voidcal(NODE*root)

(

if(root->left!=NULL)

(

cal(root->left);

cal(root->right);

switch(root->c)

(

case1+1:

root->n=root->left->n+root->right->n;

break;

case1-1:

root->n=root->left->n-root->right->n;

break;

case1*1:

root->n=root->left->n*root->right->n;

break;

case1/1:

root->n=root->left->n/root->right->n;

)

}

)

NODE*build();

NODE*getunit()

(

NODE*a;

if(s[cur]==1(1)

(

cur++;

a=build();

)

else

(

a=newNODE;

a->n=s[cur]-f01;

14

cur++;

)

returna;

)

NODE*getexpr()

(

NODE*az*b,*c;

a=getunit();

while(s[cur]==1*1||s[cur]==,/f)

(

b=newNODE;

b->c=s[cur];

cur++;

c=getunit();

b->left=a;

b->right=c;

a=b;

}

returna;

)

NODE*build()

(

NODE*az*b,*c;

a=getexpr();

while(s[cur]!=,\01&&s[cur]!=,)1)

(

b=newNODE;

b->c=s[cur];

cur++；

c=getexpr();

b->left=a;

b->right=c;

a=b;

)

if(s[cur]==1)1)

cur++;

returna;

)

intmain()

(

cin>>s;

15

cur=O;

tree=build();

cal(tree);

cout<<tree->n«endl;

clear(tree);

return0;

16

1递归及其实现

递归是程序设计中最常用的方法之一，许多程序设计语言都提供递归调用的功能。有些

问题用递归方法求解往往使程序非常简单清晰。栈在实现递归调用中起了关键作用。

一个直接调用自己或通过一系到的调用语句间接地调用自己的函数，称做递归函数。直

接调用自己的函数称做直接递归函数。间接调用自己的函数称做间接递归函数。

有很多数学函数是递归定义的。例如阶乘函数的递归定义是

I若n=0

Fact(n)=

nxFact(n-l)若n>0

又例如，Fibonacci(斐波那契)数列可递归定义为

0若n=0

Fib(n)=1若n=l

Fib(n-l)+Fib(n-2)若n>l

据此可以写出实现求n的阶乘和求Fibonacci数列中第n项的递归算法，如算法21和

算法22所示。

longintfect(intn){〃求非负整数n的阶乘

ifijn)return1;//0!=l

elsereturnn*fact(n-l);//n!=n*(n-l)!

}//fact

算法21求阶乘的递归算法

longintfib(intn){〃求斐波那契数列中的第n个数

if(n<2)returnn;//<O)=O,f(l)=l

elsereturnfib(n-l)+fib(n-2);//若n>1,ftn)=f(n-1)+f(n-2)

}//fib

算法22求斐波那契数的递归算法

一般地说，每个递归函数的定义都包含两个部分。

(1)递归基础

对无需递归的规模最小的问题直接进行处理。

(2)递归步骤

将•般情况的问题简化成•个或多个规模较小的同性质的问题，递归地调用同样的方法

求解这些问题，使这些问题最终简化成基础问题。

算法21的递归基础是n=0时，直接返回1(0!=1)。一般情况下，将fhct(n)简化成规

模较小的问题fact(n-l),求出fhct(n-l)后再与n相乘即求得了fect(n)

算法22的递归基础是n<2时，直接返回n(因为fib⑼=O,fib(l)=l)。•般情况"将fib(n)

17

简化成两个规模较小的问题fib（n-l）和fib（n-2）,求出Hb（n-l）和fib（n-2）之后再求它们的和即可

求出fib（n）＜,

递归函数结构清晰，程序易读，而且它们的正确性易于证明，所以递归函数是程序设计

的有力工具。为理解递归函数是如何实现的，先考察任意两个函数之间相互调用的情形。

用高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换需通过栈来进行。

通常，当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需先完

成三件事：（1）将所有的实在参数、返同地址等信息传递给被调用函数保存；（2）为被调用

函数的局部变量分配存储区；（3）将控制转移到被调用函数的入口。而从被调用函数返回调

用函数之前，系统也要先完成三件事：（1）保存被调用函数的计算结果；（2）释放被调用函

数的数据区；（3）按被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成

嵌套调用时，按照“后调用先返叫''的原则。上述函数间的信息传递和控制转移是通过“栈”

来实现的（这个栈一般称为系统工作栈），即系统将整个程序运行时所需的数据空间安排在

一个栈中，每当调用一个函数时，就为它在栈顶分配一片存储区，每当从一个函数退出时，

就释放它的存储区。所以，当前正在运行的函数的数据区必在栈顶。

•个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同

一个函数。因此，和每次调用相关的一个重要概念是递归函数运行的“层次”。假设调用该

递归函数的主函数处在第0层，则从主函数调用递归函数为进入“第1层”，从第i层递归调

用本函数为进入“下一层"，即第i+1层。在退出第i层递归时，应返回至!）“上一层"，即第

i-1层。为保证递归函数的正确执行，系统也应象在处理一般函数调用时那样，在系统工作

栈中为递归函数开辟数据存储区。每一层递归所需信息构成了一个“工作记录”，其中包括

所有的实在参数、所有的局部变量以及返回到上一层的返回地址。每进入一层递归，就产生

一个新的工作记录压入栈顶。每退出一层递归，就从栈项弹出一个工作记录。所以，当前执

行层的工作记录必定是工作栈栈顶的工作记录，称这个工作记录为“活动记录”，并称指示

活动记录的栈顶指针为“当前环境指针”（cu◎r）。图4从编译器的角度说明了阶乘函数的

18

递归实现。

5.

91E・RU<・，广rthf»rjr

2汉诺塔问题

除了某些数学函数可用递归方式定义外，一些本身具有递归特性的数据结构，如二叉树

（见第五章）等也可递归地描述。另有一类问题，虽然问题本身没力.明显的递归结构，但用

递归求解比较方便，例如汉诺塔问题。

例4（n阶Hanoi塔问题）设有A、B、C三个塔柱。在A柱上插有由小到大编号为1

到n的n个直径各不相同的圆盘，如图5（a）所示。现要求按以下规则将A柱上的n个圆

盘移到C柱上：1）每次只能移动一个圆盘；2）大盘不能压小盘；3）圆盘可以插在A、B、

C中的任一塔柱上。

可以用递归的方法求解此问题。

递归基础：当n=0时,不需要作任何操作。

19

递归步骤：当n>0时，将此问题分解成三个规模较小的问题：

(1)首先将A柱上面的n-1个圆盘移到B柱；

(2)再将A柱上最大的第n号盘移到C柱；

(3)最后将B柱上n-1个圆盘移到C柱的第n号盘之上。

如图5(b)(c)(d)所示。

111111111111

••C••C••I•,£

1,NBXMT*・**^*

据此可写出求解n(佗0)阶Hanoi塔问题的递归算法(算法23)。为方便叙述该算法的执

行过程，人为地在每条语句前添加了编号。图6展示了调用函数hanoi(2,a,b,c)的执行过程。

voidhanoi(intn,charx,chary,charz){//入II条件:n>=0

1.if(n>0){〃若n=0,则不需做任何动作，仅当n>0时

2.hanoi(n-l,x,z,y);//先将n-1个盘从x柱经z柱搬到y柱

cout«"MoveDisk"«n«"from"«x«"to"«z«endl;//将第n个盘从x搬到z

4.hanoi(n-l,y,x,z);〃再将y柱上的n-1个盘经x柱搬到z柱

5.}//if

6.}//hanoi

算法23求解汉诺塔问题的递归算法

3背包问题

设有一个背包可以放入总重量为S的物品，现有n件物品，重量分别为wl,w2.........wn。

问能否从这n件物品中选择若干件放入背包，使得放入的物品总重量恰好为S。如果存在一

组符合上述要求的物品，则称此背包问题有解(用TRUE表示问题有解)，否则称此问题无解

(用FALSE表示无解)。

20

假如我们定义一个维数组W存储各物乩的重量，用布尔函数knap(S,n)求解背包问题。

其参数S表示背包还留有的容量，n为可供选择的物品个数。显然，如果S=0,背包问题总

有解，即knap(O,n)为TRUE,因为不选择任何物品放入背包即可。当S<0时,背包问题总无

解，即knap(S,n)为FALSE,因为不论选择何物品放入背包，其总重量不会是负值。当S>0但n<l

时，背包问题也无解，因为不放任何物品到背包里，其重量之和不会是正值。假如S>0且n

>1,我们要求解背包问题有两种途径：一种是选择第n件物品放入背包，于是背包剩余的

容量为S—W[n](W[n]中存储wn,即第n件物品的重量)，可选择的物品是前n-1件。如果

knapn(s-w[n],n-l)有解，则knap(S,n)也有解，否则knap(S,n)无解，说明选择第门件物

品是错的。另一种是不选第n件物品，此时背包问题简化为knap(Sm-l),如果它有解，则

knap(S,n)也有解，如果它无解，则knap(S,n)也无解，从而背包问题可以递归地定义如下：

TRUE若S=0

knap(S,n)=FALSE若S<0或S>0且n<l

knap(S-W[n],n-l)或knap(S,n-l)若S>0且nNl

上述递归定义是确定的，因为每次递归，n总减少1,S也可能减小W[n],所以递归若干次

之后，递归基础的条件(SWO或n<l)必定成立，所以递归过程在有限步之后总能结束。

例5用递归方法求解背包问题。

根据knap(S,n)的定义，容易写出背包问题的递归算法，如算法24所示。

constintMAXN=11;〃假设最多只有十件物品

血\41^^^]={0,3,5,6,3,7,1,2,4,9,8};//假设物品的重量已存在中

intknap(ints,intn)(//s为背包的容量,n为可供选择物品的最大编号

if(s=O)returnTRUE;//若背包已装满，则有解

21

i“(s<O)||(s>O)&&(n<l))returnFALSE;〃若背包容量为负数或已无物品可选，则必无解

if(knap(S-w[n],n-l)){〃先试探将第n个物品装入背包中，若因此有解，则原题有解

cout«w[n]«"returnTRUE;}//输出背包中的第n个物品的重量

elsereturnknap(s,n-l);//不然，则舍弃第n个物品

}//knap

算法24求背包问题的递归算法

我们知道，递归函数是用栈来实现的。因此如果使用的程序设计语言不支持递归调用，

则可以利用栈来模拟递归函数的执行过程。把一个递归过程转换成一个等价的非递归过程，

现已找到了不止一种方法。这里不打算对这些方法作全面而深入的探讨，有兴趣的读者可■以

阅读参考资料[3]。应该指出，如果一个问题可用递归算法求解，则必定有非递归的算法，

因为至少可以将递归算法转换成等价的使用栈的非递归算法。然而，可能也有其它的北递归

算法。例如，背包问题也可以用非递归方法求解。用一个栈stk来模拟背包，用T记录放入

背包中的物品的总重量。从第N个物品开始，逐次检查第N个，第N-1个，…，第1个物品，

如果背包中尚有空间可放第i个物品，则将它放入背包(即将它的编号压入栈stk,并令T

增加如果放不下或虽有空间但已无可供选择的物品，则从栈中弹出一物品的编号(即

将该物品从背包中取走)，并从T中减去它的重量，然后从它的下一个(编号小1)的物品

开始，重新检查能否将它放入背包，这个过程一直进行到T中物品总重量等于S或是栈stk

的空且要检查的物品编号已小于1。结束时如T等于S则求得一解，在栈stk中的物乩(编号)

即为所选物品。

算法25描述了用非递归方法求解背包问题的算法。

intknap(intt,intn){〃t为背包的容量,n为可供选择物品的最大编号

Stacks;ETpe;inti,fbund=O;〃若找到一解,fbund被置为1,初始时found的值为0

if(t=0)returnTRUE;//背包已满，问题有解

Stacklnit(s,MAXSIZE);//假设MAXZ1SE大于n

22

while(!found&&((n>0)||!StackEmpty(s))){〃若尚未找到解且有物品可选或栈非空

if(n<=0){〃若已无物品可选，则表明先前的选择有误

Pop(s,n)；//将最近选择的物品(将其编号置入n)从背包中取出

t+=w[n];//背包的容量t因此增加w[n]

-n；//既然不能选用物品n,就试选物品n-1

}

if(n>0){〃如果还有物品可选

if(t>=w[n]){〃而且背包还能放得下

t-=w[n];〃就将物品n放入背包,t因此减少w[n]

if(!StackFull(s)){〃若栈未满

Push(s,n);〃将n入栈，即将物品n放入背包

-n;〃因此可选物品的编号小1

if(t=0)fbund=l;//若背包已满，则求得一解

)

elseexit(ERROR);〃若栈已满,则出错

}

else-n;//若背包放不下物品n,则尝试选择物品n-l

}//if(n>0)

}//while

if(found)//如果找到一解，就将所选物乩的重量输出

for(i=s.top;i>0;-i){

Pop(s,e);cout«w[e]«n}

returnfound;//返回求解结果

}//knap

算法25求背包问题的非递归算法

23

图7展示了执行kknap(13,6)时栈stk的状态变化过程。W={3,5,6,3,7,1}

4递归的效率

一般地说，虽然递归定义的函数可读性好，也易于证明其正确性，但执行效率不高。例

如，求Fibonacci数fib⑸的递归算法(算法22)的执行过程可用如图8所示的递归树(树

的定义见第五章)来描述。从图中可以看出，树中有许多重复的部分。例如,为了求fib(5),

需要二次调用fib(3),三次调用fib(2),五次调用fib(l)»如果求Rb(7),则重复的部分更多。由此

可见，fib(n)函数的效率很低。效率低的原因是在计算过程中没有保留已得到的中间结果。

例如，在求fib(4)时，已计算出fib(3)和fib(2),但退出fib(4)时仅返|可flb(4)的值，所以在调用

fib(3)时仍要重新计算。为保留中间计算结果，可以在定义fib函数时增加一些参数，例如，

可.将fib函数重新定义为newflb(n),它调用了一个辅助的递归函数Fib(first,second,n),算

法26和算法27实现了这种新的求解方法。

longintnewfib(intn){//把实质性的工作交给Fib去做

returnFib(0,l,n);

}//newfib

算法26改进的求斐波那契数的算法

longintFib(longintfirstjongintsecond,intn){〃利用参数提高递归效率

if(n=0)returnfirst;//要求的斐波那契数同first的距离为0

returnFib(second,first+se8nd,n-l);〃要求的斐波那契数同second的距离为n-1

}//Fib

算法27求斐波那契数的尾递归算法

24

RB一<7_j*U.，，V

■■aM^BIH-*P•»»»aiaiw!

*n><、9NBUHF

1iMfeN»U4■

■«•»•**”■・mai^f*A«

求Fib(0,1,5)的递归树如图3,9所示。显然只需递归调用Fib六次即可求出f5,效率比fib

要高。函数Fib(first,second,n)的工作过程可解释为：first和second是最近已计算出的两个

Fibonacci数，而n表示first和要求的数之间的距离。初始时first等于fD(f0=0),second等于

fl(fl=l),如图10(a)所示。图10(b)展示了求解Fib(o,l,5)时各递归层中first,second和n的含义。

递归函数Fib有一个特点，即被调用的Fib函数的返训值，恰恰是调用它的上一层Fib

函数的返回值，于是最低层的函数返回值直接就是最高层函数的返回值。换句话说，当函数

返回上一层时根本就不再使用上一层的局部变量，因此没有必要用栈来保留上一层的局部变

量，即可以不使用递归的方法实现同样的计算。例如算法28就是对应于算法27的非递归算

法。

longintFibo(intn)(//求斐波那契数的非递归算法

longintfirst=O,second=l,temp;intij/初始时,first=fO,second=fl

fbr(i=n；i>0;-i){//first中存储的数逐渐向第n个斐波那契数靠近

tcmp=first;first=sccond;second+=temp;{//first移向下•个斐波那契数

returnfirst;//for语句结束时,first已是第n个斐波那契数

}//Fibo

算法28求斐波那契数的非递归算法

显然，也可以用图10来解释Fibo的执行过程。由于Fibo消除了递归，省掉了n次函

数调用的开销，所以它的效率更高。

尾递归函数是一种特殊的递归函数。如果一个递归函数的返回值是直接计算而得或恰是

25

一个递归调用1tl身而得到的返回值，那么这个递归函数就称为尾递归函数。换句话说，如果

递归函数中有一个递归调用(自身)的语句是这个函数的最后••个可执行语句，那么这个函

数就被称做尾递归函数。应该注意，最后一个可执行语句并不一定是程序中的最后一条语句。

例如，Fib的返回值或者是first(若n=0),或者是递归调用Fib的返回值，所以它是尾递归

函数。从算法27中也可以看出。Fib函数中的递归调用语句是最后一个可执行语句。

尾递归函数是一类重要的函数，一方面它的效率一般较高，例如算法27的效率比算法

22的效率高。另一方面，很容易消除尾递归函数中的递归，使之成为非递归函数，从而不

需要用栈来保留每个递归副本的局部变量，例如算法28比算法27效率更高。

例6用尾递归实现阶乘函数，并消除递归。

算法29和算法30是用尾递归实现阶乘函数的算法。算法31是求n的阶乘的非递归算

法。

longintnewfact(intn){〃入口条件:n>=0,把实质性工作交给Fact去做

returnFact(1,n);//

}//newfact

算法29另一种求阶乘算法

longintFact(longintresult,intn){〃入口条件:定0,第1次调用时jesult应为1

ifl：n<=l)returnresult;

returnFact(result*n,n-1);

}//Fact

算法30求阶乘的尾递归算法

longintFactor(intn)