递归算法详解

1、冯文科一、递归的基本概念。一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态这种用自己来定义自己的方法，称之为递归或递归定义。 在程序设计中，函数直接或间接调用自己，就被称为递归调用。二、递归的最简单应用：通过各项关系及初值求数列的某一项。在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及an与前面临近几项之间的关系。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各 项的关

2、系。比如阶乘数列1、2、6、24、120、720如果用上面的方式来描述它，应该是：1,n 1nan i,n 1如果需要写一个函数来求 an的值，那么可以很容易地写成这样:int f(int n)if(n=1)return 1;return n*f(n-1);这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况一一这也是递归函数的第一个出口，再处理递归关系一一这形成递归函数的第二个出口。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果， 再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。以上面求阶乘

3、数列的函数 f(n)为例。如在求f(3)时，由于3不是特殊值，因此需要计算3* f(2),但f (2)是对它自己的调用，于是再计算f (2) , 2也不是特殊值，需要计算2* f (1),需要知道f(1)的值，再计算f (1) , 1是特殊值，于是直接得出f (1) 1 ,返回上步，得 f (2) 2* f (1) 2 ,再返回上一步，得f (3) 3* f(2) 3*2 6 ,从而得最终解。用图解来说明，就是f (3)的执行过程(特殊值判断：)3 1 ,继续向下。(递归关系处理：)(特殊值判断：)2 1,继续向下。(递归关系处理：)f (2)的执行过程f (1)的执行过程(特殊值判断：)1

4、1 ,由特殊情况出口直接返回1。求3* f (2),需要先求2* f(1),需要先计算f(2),调用且本身挂起常出口返回3*2得到f (2) 2,由正计算f(1),调用且本身挂起得到f(1) 1 ,由正常出口返回2*1卜面再看一个稍复杂点的例子。【例1】数列a。的前几项为1、111 1输入n ,编程求an的精确分数解。分析：这个题目较易，发现a1 1,其它情况下有an1、。如要求实数解的话，这基本1 an 1已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设an 1 9 ,P则由递归关系，有an11 an 1p,再约分化简，即得an。但发现一个问题: p q求出an 1时，

5、需要返回两个整数：分子 q与分母p,而通常的函数只能返回一个整数。这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了（其实还可以不只两个呢）；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。 但由于后一种做法会使程序结构不清晰一一返回值是 由参数表得到的，因此我们使用前一种方法。另外，在通过an i q得出an p后，an就已经是最简分数了，无须化简。证明 pp q如下：若q是最简分数，即说明p, q的最大公约数为1,即对任何1 r q ,都有q mod r与 Ppmod r不全为 0,不防记 q mod r a、pmod r

6、b ,则有（p q） mod r （a b） mod r只要a与b不全为0,且a r, b r ,就有a与（a b） mod r不全为0。因此对任何的1 r q,有 pmodr 与（p q）mod r 不全为 0。而对于q r p的情况而言，记 p mod r a ,则有（p q） mod r （a q） mod r由于0 a r ,0 q r ,因此同样有 pmodr与（p q） mod r不全为0。所以对任意1 r p ,者B有pmodr与（p q）mod r不全为0,因此它们的最大公约数为1,即一p-是最简分数。虽然这是个要求 an 1 （即q）是最简分数的结论，但由于数 p qp1列第

7、二项为1,是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的 an,2求出的一p-就是最简分数，无须化简。p q具体代码如下：/ Exam1.cpp#include <iostream>using namespace std;struct FSunsigned long long q, p;；FS f(int n)FS r;if(n=1)r.q=1;r.p=1;return r;r=f(n-1);r.p=r.p+r.q;r.q=r.p-r.q;return r;int main()FS r;int n;cin>>n;r=f(n);cout<<r.

8、q<<'/'<<r.p<<endl;system("pause");return 0;三、递归的精髓：只考虑当前一步，剩下的让下一步去做吧。对大多数问题而言，当它的规模缩小至“特殊情况”时，都可以非常轻易地得出问题的解，因此我们不过多地讨论“特殊情况”，只详细地讨论递归关系的确定。寻找递归关系，最低标准是它能使问题的规模变小，且变小后的问题与原问题在本质上是一样的。当找到递归关系后， 我们的递归函数只须处理特殊情况与递归关系，不需要处理其它的信息一一至于下一步的事情，就让下一步去做吧。另一个需要考虑的事情就是递归函数的参数

9、表，首先，在通常情况下，参数表都要使用变量参数，且递归函数中尽量使用局部变量一一这会减少很多不必要的麻烦；其次，参数表中，大多都有一个表示当前在执行第几步的参数。【例2】下图是一个有向图，输入 N(0 N 9),打印0 N的所有路径。分析：仔细研究这个图的特点，发现以下规律：对任何结点i,都可以走到i 1和i 2,当然如果它们不超过9的话。由于要打印路径，因此需要保存查找过程中的部分路径信息。可以做一个全局数组path口来存储这个信息，由于结点 0没有来路，且是所有路径的起点，因此记path0=0 ,递归函数负责填写之后的路径结点。我们这样设计递归函数：首先，这个递归函数的参数表中至少需要一个

10、参数i ,它的意义是表示现在在填路径中的第几个结点，而pathi可以填的数，要么是上一个结点加1,要么是上一个结点加2,即 pathi=pathi-1+1 或 pathi=pathi-1+2 ；其次，特殊情况的讨论：我们要找的是终止到N的路径，因此若出现pathi-1= N的情况，就说明已经找到路径，无须将当前层再填入结点，可以将 path中的信息输出并结束 函数了一一这是递归函数的特殊情况出口 ；第三、递归关系的处理：若还没到达结点N ,则填写本结点pathi,上文已说明，pathi=pathi-1+1 或pathi=pathi-1+2 ,当然如果它们都不过9的话。将结点i填好后，说明路径向

11、下走了一步，距离结点 N更近了一步，问题规模已经变小。不要处理其 它东西，直接递归，通过递归调用去填写i+1结点就可以了。这里有处和【例1】不相同的地方，即 pathi是有两种可能可选的，我们的处理这这 样的，先令pathi=pathi-1+1 ,然后递归调用，填写i+1结点，当这个调用返回时，说 明所有pathi为pathi-1+1的路径都已经讨论完成了，再令 pathi=pathi-1+2 ,再递归，当它返回时，整个函数执行完毕，形成正常的执行完成时的出口。具体代码如下：/ Exam2.cpp #include <iostream> using namespace std;#d

12、efine MAX 9 int pathMAX, N;int write(int i)int j;for(j=0;j<i;j+)cout<<pathj<<"->"cout<<pathi<<endl;void f(int i)if(pathi-1=N)write(i-l);return;if(pathi-1+1<=N)pathi=pathi-1+1;f(i+1)；if(pathi-1+2<=N)pathi=pathi-1+2;f(i+1)；int main()cin>>N;path0=0;f(

13、1)；system("pause");return 0;【例3】我的画笔。Windows中的画笔从 Windows3.x时代开始就已经有了，虽然功能与Photoshop不能相比，但它小巧而迅速，一般的简单功能还是很方便的。画笔中的填色工具是油漆桶，选定它，再指定一个颜色，在图片中一点，所有与这个点颜色相同且相连的象素就都被填充了。如下图示：画笔的油漆桶工具填充的是一个叫“四连通”的区域，即它只从上、下、左、右四个方 向向外扩展。请编写程序，模拟油漆通工具。输入文件：Exam3In.txt中有10行，每行是一个10字符的字符串，表示一个 10*10的 图象，不同的字符表示不同

14、的颜色；之后的一行有两个用空格分开的整数，表示油漆桶点中 的位置，再后面一行是一个字符，表示油漆桶的填充颜色。输出文件：Exam3Out.txt ,输出10行，每行10个字符的字符串，表示填充后的图象。 分析：本题给了一个点的位置，查找所有与它“四连通”的点就成为本题的核心问题。我们的算法是这样的：先从这个起点出发，沿四个方向展开，看这“直接相连”的四个点是否可以 填充，若有可以的，则再以这个点为中心，再向四个方向展开直到所有可能展开的点都不能再展开了为止。递归函数这样设计：首先它的参数表需要两个参数， 表示本次从哪个位置点展开； 其次, 依次讨论它四个方向上相邻的点是否可填充一一与起点颜色相

15、同，如果可以，则填充，并以此点为中心，递归调用。代码如下：/ Exam3.cpp#include <fstream> using namespace std;#define N 10ifstream fin("Exam3In.txt");ofstream fout("Exam3Out.txt");char picNN+1, c, p; int col, row;void fill(int i, int j)if(i-1>=0 && pici-1j=p)pici-1j=c;fill(i-1, j);if(i+1<N

16、&& pici+1j=p)pici+1j=c;fill(i+1, j);if(j-1>=0 && picij-1=p)pic皿-1=c;fill(i, j-1);if(j+1<N && picij+1=p)pic皿+1=c;fill(i, j+1)； int main() int i;for(i=0;i<N;i+)fin>>pici;fin>>row>>col; fin>>c;p=picrowcol;picrowcol=c; fill(row, col);for(i=0;i<

17、N;i+)fout<<pici<<endl;return 0; 本题中的递归函数fill似乎与常规的递归函数比较起来缺少了处理特殊情况的部分，其实不然，它的特殊情况处理已经被融合到递归关系的处理当中了，正常与非正常的出口合并到一起。特殊情况就是：当向四个方向都无法展开时，程序直接退出。这个程序的fill函数运用的算法就是“种子填充算法”的递归写法。它另有动态规划 的写法一一当然比这个要快得多，大家可以想一想如何实现。四、递归函数的必然用法：处理递归定义的数据结构。一些常用的数据结构本身就是递归定义的，写一个递归的函数来处理它，当然是再正常不过的事情，就比如说二叉树、广义

18、表【例4】二叉树的操作。用字符串的形式给定一个完全二叉树，保存在输入文件Exam4In.txt中，编写程序输出其后序遍历的结果至输出文件Exam4Out.txt中。分析：本题的程序是简单的，唯一要注意的是：C+的数组从下标0开始，因此对于结点i,它的左孩子编号应该是 2i 1,右孩子编号应该是2(i 1)。其它的地方没什么难度。代码如下：/ Exam4.cpp#include <fstream> using namespace std;#define M 100ifstream fin("Exam4In.txt");ofstream fout("Exa

19、m4Out.txt");char treeM;int L;void run(int i)if(2*i+1<L)run(2*i+1);if(2*(i+1)<L)run(2*(i+1); fout<<treei;int main()fin>>tree;L=strlen(tree);run(0);return 0;【例5】以字符串形式给出一棵完全二叉树的先序遍历与中序遍历序列，编程输出用字符串 形式表示的完全二叉树的结构。分析：先序遍历的首结点一定是整棵树的根，因此可以直接标在 0处。在中序遍历序列中， 它左边的结点构成左子树，右边的结点构成右子树，从而

20、可以知道，左子树与右子树的结点个 数，进而得到及左子树与右子树的先序遍历与中序遍历序列，递归查找所有子树的根即可。为了得到整棵树的结构，设置全局数组tree口来存储，全局数组 s口的意义是：si存储整数表示第i层结点的起始下标。代码如下：/ Exam5.cpp#include <fstream> using namespace std;#define M 100ifstream fin("Exam5In.txt");ofstream fout("Exam5Out.txt");char preM, midM, treeM;int L, sM;v

21、oid build(int layer, int ps, int pe, int ms, int me)treeslayer=preps;slayer+;if(ps=pe)return;int i;i=ms;while(midi!=preps)i+；build(layer+1, ps+1, ps+i-ms, ms, i-1);build(layer+1, ps+i-ms+1, pe, i+1, me);int main()fin>>pre>>mid;L=strlen(pre);s0=0;int i, j;i=1;j=2;while(si<L)si=j-1;j=j*

22、2;i+;build(0, 0, L-1,0, L-1);treeL='0'fout<<tree;return 0;五、递归与回溯法。递归的另一个常用的地方是实现回溯法。所谓回溯法，一般就是指先将问题分成几步，在每一步时尝试所有的可能，直到达到最终要求，或最后一步将所有可能尝试完成后，再回到上一步，使上一步尝试下一种可能，并继续的作法。由于回溯的“步骤性”明显，因此用递归实现回溯是相当方便的事。看下面的一个例题:【例6】n皇后问题。输入整数n,打印n皇后问题的所有解及解的总数。代码如下：/ Exam6.cpp#include <iostream>usin

23、g namespace std;#define MAX 100int n, qMAX, c;bool markMAX;void write()int i;char tMAX;memset(t, '.', MAX*sizeof(char);tn尸0'for(i=0;i<n;i+)tqi='Q'cout<<t<<endl;tqi='.'cout<<endl;bool test(int i, int k)int j;j=0;while(j<k && abs(j-k)!=abs(qj

24、-i)j+;if(j=k && marki=false)return true;elsereturn false;void search(int k)if(k=n)write();c+;return;int i;for(i=0;i<n;i+)if(test(i, k)marki=true;qk=i;search(k+1);marki=false;int main()cin>>n;memset(mark, 0, MAX*sizeof(bool);c=0;search(0);cout<<c<<endl;system("pause&

25、quot;);return 0;39六、练习【练习】为给定的表达式建立表达式树，并求值。给定的表达式中，所有数字都是1位正整数，出现的符号可能为十、一、*、/、（、）。分析：这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。在详细说明这个算法之前，需要首先明确这个算法用到的概念1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数；2、项：一个项是指由*与/连接起来的若干单元；3、表达式：一个表达式是指由+或-连接起来的若干项。要建立表达式树，需要三个函数互相调用的函数：一个是getunit ,用于建立一个单元；一个是getexpr ,用于建立一个项，另一个就是build ,

26、用于建立一个表达式。getunit函数较易，如果字符串首字母是（的话，那么从它后面的字符开始用build建立一个表达式，这个表达式就是一个单元；否则，就处理一个整数；getexpr函数是建立在getunit之上的，它先用getunit 建立一个单元，然后不停地考 察之后地连接符号是不是 *或/,若是，则不停地重复读连接符、 建立另一个单元、建立连接 的操作，直到连接符号不是 *或/为止。build函数是用于最终建立表达式的，它先用 getexpr建立一个项，再用符号将剩余的 各项连接成二叉树。代码如下：/ Exer.cpp#include <iostream>using names

27、pace std;struct NODEint n;char c;NODE *left, *right;NODE（） left=NULL;right=NULL; ;char s100;int cur;NODE *tree;void clear(NODE *root) if(root=NULL) return;clear(root->left);clear(root->right); delete root; void cal(NODE *root)if(root->left!=NULL)cal(root->left);cal(root->right);switch

28、(root->c)case '+':root->n=root->left->n+root->right->n; break;case '-':root->n=root->left->n-root->right->n; break;case '*':root->n=root->left->n*root->right->n;break;case '/':root->n=root->left->n/root->righ

29、t->n;NODE *build();NODE *getunit()NODE *a;if(scur='(')cur+;a=build();elsea=new NODE;a->n=scur-'0'cur+; return a;NODE *getexpr()NODE *a, *b, *c;a=getunit();while(scur='*' | scur='/')b=new NODE;b->c=scur;cur+;c=getunit();b->left=a;b->right=c;a=b;return a;

30、NODE *build()NODE *a, *b, *c;a=getexpr();while(scur!='0' && scur!=')')b=new NODE;b->c=scur;cur+;c=getexpr();b->left=a;b->right=c;a=b;if(scur=')')cur+;return a;int main()cin>>s;cur=0;tree=build();cal(tree);cout<<tree->n<<endl;clear(tree);r

31、eturn 0;1 递归及其实现递归是程序设计中最常用的方法之一，许多程序设计语言都提供递归调用的功能。有些 问题用递归方法求解往往使程序非常简单清晰。栈在实现递归调用中起了关键作用。一个直接调用自己或通过一系到的调用语句间接地调用自己的函数，称做递归函数。直接调用自己的函数称做直接递归函数。间接调用自己的函数称做间接递归函数。有很多数学函数是递归定义的。例如阶乘函数的递归定义是1若 n=0Fact(n)=nXFact(n -1) 若 n>0Fibonacci( 斐波那契) 数列可递归定义为0若 n=0Fib(n) =1若 n=1Fib(n-1)+Fib(n-2) 若 n>1据此可

32、以写出实现求n 的阶乘和求Fibonacci 数列中第n 项的递归算法，如算法21 和算法 22 所示。/ 求非负整数n 的阶乘/0!=1/n!=n*(n-1)!/ 求斐波那契数列中的第/f(0)=0,f(1)=1/ 若 n>1,f(n)=f(n-1)+f(n-2)n 个数long int fact(int n)if(!n) return 1;else return n*fact(n-1);/fact算法 21 求阶乘的递归算法long int fib(int n)if(n<2) return n;else return fib(n-1)+fib(n-2);/fib算法 22 求斐

33、波那契数的递归算法一般地说，每一个递归函数的定义都包含两个部分。(1) 递归基础对无需递归的规模最小的问题直接进行处理。(2) 递归步骤将一般情况的问题简化成一个或多个规模较小的同性质的问题，递归地调用同样的方法求解这些问题，使这些问题最终简化成基础问题。算法 21 的递归基础是n=0 时，直接返回1 ( 0！ =1) 。一般情况下，将fact(n) 简化成规模较小的问题fact(n-1) ，求出 fact(n-1) 后再与 n 相乘即求得了fact(n) 。fib(n)算法22的递归基础是n<2时，直接返回n (因为fib(0)=0,fib(1)=1)。一般情况下，将简化成两个规模较小

34、的问题fib（n-1） 和 fib（n-2）, 求出 fib（n-1） 和 fib（n-2） 之后再求它们的和即可求出 fib（n） 。递归函数结构清晰，程序易读，而且它们的正确性易于证明，所以递归函数是程序设计的有力工具。为理解递归函数是如何实现的，先考察任意两个函数之间相互调用的情形。用高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换需通过栈来进行。通常，当一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成三件事：（ 1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（ 2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调用函数的入口。而从

35、被调用函数返回调用函数之前，系统也要先完成三件事：（ 1）保存被调用函数的计算结果；（ 2）释放被调用函数的数据区；（3）按被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则。上述函数间的信息传递和控制转移是通过“栈”来实现的（这个栈一般称为系统工作栈），即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一片存储区，每当从一个函数退出时，就释放它的存储区。所以，当前正在运行的函数的数据区必在栈顶。一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个

36、重要概念是递归函数运行的“层次”。假设调用该递归函数的主函数处在第。层，则从主函数调用递归函数为进入“第 1层”，从第i层递归调用本函数为进入“下一层”，即第 i+1 层。在退出第i 层递归时，应返回到“上一层”，即第i-1 层。为保证递归函数的正确执行，系统也应象在处理一般函数调用时那样，在系统工作栈中为递归函数开辟数据存储区。每一层递归所需信息构成了一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及返回到上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈项弹出一个工作记录。所以，当前执行层的工作记录必定是工作栈栈顶的工作记录，称这个工作记录为

37、“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”（ curptr ） 。图 4 从编译器的角度说明了阶乘函数的递归实现。ffi4 AttKHHIAFtl2汉诺塔问题除了某些数学函数可用递归方式定义外，一些本身具有递归特性的数据结构，如二叉树（见第五章）等也可递归地描述。另有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比较方便，例如汉诺塔问题。例4 （n阶Hanoi塔问题）设有A B、C三个塔柱。在 A柱上插有由小到大编号为 1到n的n个直径各不相同的圆盘，如图 5 （a）所示。现要求按以下规则将 A柱上的n个圆盘移到C柱上：1）每次只能移动一个圆盘；2）大盘不能压小盘；3）

38、圆盘可以插在 A、BC中的任一塔柱上。可以用递归的方法求解此问题。递归基础：当n=0时,不需要作任何操作。递归步骤：当n>0时，将此问题分解成三个规模较小的问题：(1)首先将A柱上面的n-1个圆盘移到B柱；(2)再将A柱上最大的第n号盘移到C柱；(3)最后将B柱上n-1个圆盘移到C柱的第n号盘之上。如图5(b)(c)(d) 所示。ill llllli 山一 曲目 C 鼻 RC Al B C曲& £|用咒 AM id 出1 fI 4电bC 隹fflt据此可写出求解n(n)0)阶Hanoi塔问题的递归算法(算法23)。为方便叙述该算法的执行过程，人为地在每条语句前添加了编号

39、。图6展示了调用函数hanoi(2,a,b,c) 的执行过程。void hanoi(int n,char x,char y,char z)入口条件：n>=01. if(n>0)/ 若 n=0,则不需做任何动作，仅当n>0时2. hanoi(n-1,x,z,y);/ 先将 n-1 个盘从 x 柱经z柱搬到y柱cout<<"Move Disk "<<n<<" from "<<x<<" to "<<z<<endl;将第 n 个盘从 x 搬到

40、 z4. hanoi(n-1,y,x,z);/ 再将 y 柱上的 n-1 个盘经x柱搬到z柱5. /if6. /hanoi算法23求解汉诺塔问题的递归算法3背包问题设有一个背包可以放入总重量为S的物品，现有n件物品，重量分别为 w1 , w2,，wn 。&如果存在一问能否从这n件物品中选择若干件放入背包，使得放入的物品总重量恰好为组符合上述要求的物品，则称此背包问题有解(用TRUElt示问题有解)，否则称此问题无解(用FALSER示无解)。假如我们定义一个维数组 W存储各物品的重量,用布尔函数knap(S,n)求解背包问题。其参数S表示背包还留有的容量，n为可供选择的物品个数。显然，如

41、果S=0,背包问题总有解，即knap(0,n)为TRUE因为不选择任何物品放入背包即可。当 S<0时，背包问题总无解，即knap(S,n)为FALSE,因为不论选择何物品放入背包，其总重量不会是负值。当 S>0但n<1时，背包问题也无解，因为不放任何物品到背包里，其重量之和不会是正值。假如S>0且n>1,我们要求解背包问题有两种途径：一种是选择第n件物品放入背包，于是背包剩余的容量为S- Wn(Wn中存储wn ,即第n件物品的重量),可选择的物品是前 n-1件。如果knapn(s-wn,n-1) 有解，则knap(S,n)也有解，否则knap(S,n)无解，说明选

42、择第 n件物品是错的。另一种是不选第n件物品，此时背包问题简化为knap(S,n-1),如果它有解，则knap(S,n)也有解，如果它无解，则knap(S,n)也无解，从而背包问题可以递归地定义如下：TRUE若 S=0knap( S,n) =FALSE若 S<0 或 S>0 且 n<1knap(S-Wn,n-1) 或 knap(S,n-1)若S>0且 n>l上述递归定义是确定的，因为每次递归，n总减少1, S也可能减小 Wn,所以递归若干次之后，递归基础的条件(SKO或n<1)必定成立，所以递归过程在有限步之后总能结束。例5用递归方法求解背包问题。根据kna

43、p(S,n)的定义，容易写出背包问题的递归算法，如算法 24所示。/ 假设最多只有十件物品const int MAXN=11;int wMAXN=0,3,5,6,3,7,1,2,4,9,8; /假设物品的重量已存在w1.w10中int knap(int s,int n)/ s 为背包的容量,n 为可供选择物品的最大编号if(s=0) return TRUE;/ 若背包已装满, 则有解if(s<0)|(s>0)&&(n<1)return FALSE;/若背包容量为负数或已无物品可选, 则必无解if(knap(s-wn,n-1)/ 先试探将第n 个物品装入背包中,

44、 若因此有解, 则原题有解cout<<wn<<" " return TRUE;/ 输出背包中的第n 个物品的重量else return knap(s,n-1);/ 不然 , 则舍弃第n 个物品/knap算法 24 求背包问题的递归算法我们知道，递归函数是用栈来实现的。因此如果使用的程序设计语言不支持递归调用，则可以利用栈来模拟递归函数的执行过程。把一个递归过程转换成一个等价的非递归过程，现已找到了不止一种方法。这里不打算对这些方法作全面而深入的探讨，有兴趣的读者可以阅读参考资料3 。应该指出，如果一个问题可用递归算法求解，则必定有非递归的算法，因为至

45、少可以将递归算法转换成等价的使用栈的非递归算法。然而，可能也有其它的非递归算法。例如，背包问题也可以用非递归方法求解。用一个栈stk 来模拟背包，用T 记录放入背包中的物品的总重量。从第 N个物品开始，逐次检查第 N个，第N-1个，第1个物品，如果背包中尚有空间可放第i 个物品，则将它放入背包(即将它的编号压入栈stk ，并令 T增加 Wi ) 。如果放不下或虽有空间但已无可供选择的物品，则从栈中弹出一物品的编号(即将该物品从背包中取走)，并从 T 中减去它的重量，然后从它的下一个(编号小1 )的物品开始，重新检查能否将它放入背包，这个过程一直进行到T 中物品总重量等于S 或是栈 stk的空且

46、要检查的物品编号已小于1 。结束时如T 等于S 则求得一解，在栈stk 中的物品( 编号 )即为所选物品。算法 25 描述了用非递归方法求解背包问题的算法。int knap(int t,int n)编号/ t 为背包的容量,n 为可供选择物品的最大Stack s; ETp e; int i,found=0;/若找到一解,found 被置为 1, 初始时 found 的值为 0if (t=0) return TRUE;/ 背包已满, 问题有解StackInit(s,MAXSIZE);/假设MAXZISE大于nwhile (!found&&(n>0)|!StackEmpty(

47、s)/if (n<=0) 可选 , 则表明先前的选择有误Pop(s,n);从背包中取出t+=wn;容量 t 因此增加wn-n;既然不能选用物品n, 就试选物品n-1if (n>0) 品可选if (t>=wn) 下t-=wn;品 n 放入背包,t 因此减少wn若尚未找到解且有物品可选或栈非空/ 若已无物品/ 将最近选择的物品（将其编号置入n）/ 而且背包还能放得/ 背包的/ 如果还有物/ 就将物/即将物品n 放入背包if (!StackFull(s)Push(s,n);/ 若栈未满/ 将 n 入栈 ,因此可选物品的编号小1-n；/if (t=0) found=1;/若背包已满，

48、则求得一解else exit(ERROR);else -n;放不下物品n,则尝试选择物品n-1/if(n>0)/whileif (found)解，就将所选物品的重量输出for (i=s.top; i>0; -i)Pop(s,e); cout<<we<<"" return found;/knap算法25求背包问题的非递归算法图7展示了执行kknap(13,6)时栈stk的状态变化过程。/若栈已满，则出错/若背包/如果找到一/返回求解结果W=3,5,6,3,7,1I I F4 递归的效率一般地说，虽然递归定义的函数可读性好，也易于证明其正确性

49、，但执行效率不高。例如，求Fibonacci数fib（5）的递归算法（算法22）的执行过程可用如图 8所示的递归树（树的定义见第五章)来描述。从图中可以看出，树中有许多重复的部分。例如，为了求fib (5),需要二次调用fib(3),三次调用fib(2),五次调用fib(1)。如果求fib(7),则重复的部分更多。由此 可见，fib(n)函数的效率很低。效率低的原因是在计算过程中没有保留已得到的中间结果。例如，在求fib(4)时，已计算出fib(3)和fib(2),但退出fib(4)时仅返回fib(4)的值，所以在调用fib(3)时仍要重新计算。为保留中间计算结果，可以在定义fib函数时增加一

50、些参数，例如，可将fib函数重新定义为newfib(n),它调用了一个辅助的递归函数Fib(first, second, n) ,算法26和算法27实现了这种新的求解方法。long int newfib(int n)/把实质性的工作交给Fib去做return Fib(0,1,n);/newfib算法26改进的求斐波那契数的算法long int Fib(long int first,long int second,int n)/利用参数提高递归效率if(n=0) return first;/要求的斐波那契数同first 的距离return Fib(second,first+second,n-1)

51、;/Fib算法27求斐波那契数的尾递归算法要求的斐波那契数同 second的距离为n-1Ite* _ a _ 中由曰fsh十6tib；i 工 由二法1cH 曲力 为 FifafXi Pf riHDrmiiAi hK i mpi+Jw庄* ruuirAJH求Fib(0,1,5)的递归树如图3,9所示。显然只需递归调用Fib六次即可求出f5,效率比fib要高。函数Fib(first, second, n)的工作过程可解释为：first 和second是最近已计算出的两个Fibonacci数，而n表示first和要求的数之间的距离。初始时 first 等于f0 (f0=0),second 等于f1

52、(f1=1), 如图10(a)所示。图10(b)展示了求解Fib(o,1,5)时各递归层中first, second 和n的含义Fib递归函数Fib有一个特点，即被调用的 Fib函数的返回值，恰恰是调用它的上一层函数的返回值，于是最低层的函数返回值直接就是最高层函数的返回值。换句话说，当函数返回上一层时根本就不再使用上一层的局部变量，因此没有必要用栈来保留上一层的局部变量，即可以不使用递归的方法实现同样的计算。例如算法28就是对应于算法27的非递归算法。long int Fibo(int n)/求斐波那契数的非递归算法long int first=0, second=1, temp; int

53、i;/初始时，first=f0,second=f1for(i=n;i>0;-i)/first中存储的数逐渐向第 n个斐波那契数靠近temp=first; first=second; second+=temp;first移向下个斐波 契数return first;/for 语句结束时first 已是第n个斐波那契数/Fibo算法28求斐波那契数的非递归算法显然，也可以用图10来解释Fibo的执行过程。由于 Fibo消除了递归，省掉了 n次函 数调用的开销，所以它的效率更高。尾递归函数是一种特殊的递归函数。如果一个递归函数的返回值是直接计算而得或恰是一个递归调用自身而得到的返回值，那么这个递

54、归函数就称为尾递归函数。换句话说，如果递归函数中有一个递归调用(自身)的语句是这个函数的最后一个可执行语句，那么这个函数就被称做尾递归函数。应该注意，最后一个可执行语句并不一定是程序中的最后一条语句。例如，Fib的返回值或者是first (若n=0),或者是递归调用 Fib的返回值，所以它是尾递归函数。从算法27 中也可以看出。Fib 函数中的递归调用语句是最后一个可执行语句。尾递归函数是一类重要的函数，一方面它的效率一般较高，例如算法27 的效率比算法22 的效率高。另一方面，很容易消除尾递归函数中的递归，使之成为非递归函数，从而不需要用栈来保留每个递归副本的局部变量，例如算法28 比算法 27 效率更高。例 6 用尾递归实现阶乘函数，并消除递归。算法 29 和算法 30 是用尾递归实现阶乘函数的算法。算法31 是求 n 的阶乘的非递归算法。long int newfact(int n)/ 入口条件: