本文所属图书&>&
作者长期从事程序设计语言和数据结构课程的基础教学工作，本书是在总结这些教学经验的基础上编写而成，全书分为12章，包括绪论、线性表、栈和队列、串、数组和稀疏矩阵、递归、树形结构、广义表、查找、内排序、...&&
4 &知识点4：递归
3.4.1 &要点归纳
1. 递归的定义
在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归，所有的间接递归都可以转化成直接递归，本章只讨论直接递归。递归算法指的是包含递归过程的算法。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。例如，以下算法是一个求n!的尾递归算法：
int fun(int n)
{&& if (n==1)
&&&&&&& return(1);
&&&&&&& return(n*fun(n-1));
2. 递归模型
递归模型是递归算法的抽象，它反映一个递归问题的递归结构，例如，前面的求n!对应的递归模型如下：
f(1)=1&&&&&&&&&&&&&&&&&&& &&&&(1)
f(n)=n*f(n-1)&&& n&1&&&&&&& (2)
其中，第一个式子给出了递归的终止条件，第二个式子给出了f(n)的值与f(n-1)的值之间的关系，把第一个式子称为递归出口，把第二个式子称为递归体。
实际上，递归思路是把一个不能或不好直接求解的&大问题&转化成一个或几个&小问题&来解决，再把这些&小问题&进一步分解成更小的&小问题&来解决，如此分解，直至每个&小问题&都可以直接解决（此时分解到递归出口）。但递归分解不是随意的分解，递归分解要保证&大问题&与&小问题&相似，即求解过程与环境都相似。
为了讨论方便，简化的递归模型如下：
f(s1)=m1&&&
f(sn)=g(f(sn-1),c)
求f(sn)的分解过程如下：
&&& f(sn-1)
一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是&量变&过程，即原来的&大问题&在慢慢变小，但尚未解决，遇到递归出口后，便发生了&质变&，即原递归问题便转化成直接问题。上面的求值过程如下：
&&& f(s1)=m1
&&& f(s2)=g(f(s1)，c1)
&&& f(s3)=g(f(s2)，c2)
&&& f(sn)=g(f(sn-1)，cn-1)
这样f(sn)便计算出来了，因此，递归的执行过程由分解和求值两部分构成。
归纳起来，递归调用的实现是分两步进行的：第一步是分解过程，即用递归体将&大问题&分解成&小问题&，直到递归出口为止；然后进行第二步的求值过程，即已知&小问题&，计算&大问题&。对于前面的递归算法，fun(5)求解过程如图3.16所示。对于复杂的递归调用则是这两个步骤的循环反复，直到求出最终值。
图3.16 &fun(5)的求解过程
上述f(n)是一个简单的递归算法，对于复杂的递归算法，其求解过程可能十分复杂：分解中包含求值，求值中包含分解。递归问题的求解过程构成一棵递归树。
3. 递归算法的设计
递归的求解过程均有这样的特征：先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程，这是一种分而治之的算法设计方法。
（1）简单递归算法设计方法
对于比较简单的递归算法，其一般设计步骤如下：
对原问题f(s)进行分析，假设出合理的&较小问题&f(s')。
假设f(s')是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s')之间的关系。
确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口。
例如，采用递归算法求实数数组A[0..n-1]中的最小值。假设f(A,i)函数求数组元素A[0..i]中的最小值，则f(A,i-1)函数求数组元素A[0..i-1]中的最小值，前者为&大问题&，后者为&小问题&。当i=0时，有f(A,i)=A[0]。假设f(A,i-1)已求出，则f(A,i)=MIN(f(A,i-1),A[i])，其中MIN()为求两个值中的较小值函数。因此得到如下递归模型：
&&&&&&&&& &&&&&&&&&&&&&&&&&&&A[0]&&&&&&&&&&&&&&&&&&&&&&&&&& 当i=0时
&&&&&&&&&&&& &&&&&&&&&&&&&&&&MIN(f(A,i-1),A[i])&&&& 其他情况
由此得到如下递归求解算法：
double f(float A[],int i)
&&& if (i==0)&&&&&&&&&&& & //当i=0时返回A[0]
&&&&&&& return A[0];
&&& else&&&&&&&&&&&&&&& && //当i&0时返回MIN(f(A,i-1),A[i])
&&& {&& m=f(A,i-1);
&&&&&&& if (m&A[i])
&&&&&&&& &&&return A[i];
&&&&&&& else
&&&&&&&&&&&
（2）复杂递归算法设计方法
递归问题的参数构成了递归状态。对于较复杂的递归问题，常常采用试探方法。假设递归求解过程从状态s0到状态sn，求解的一般步骤如下：
假设当前状态为si，将si的环境设置为已处理过。
求出从si出发可以到达的某状态sj，若sj=sn，输出一个解；否则递归调用sj，表示从sj开始处理。
若从si出发不能到达任何状态，则回溯，将si的环境设置为未处理过（称为恢复环境）。
例如，对于前面介绍的迷宫问题，输出所有路径的递归过程如下（另设置一个Path数组存放路径，d为其当前下标，从0开始）：
void mgpath(int x1,int y1,int x2,int y2,int d)&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& //路径为:(x1,y1)-&(x2,y2)
{&& mg[x1][y1]=-1;&&&&&&&&&&&&&&&&&&& & //将(x1,y1)设置为已搜索过
&&& while (找(x1,y1)的所有相邻方块(i,j))
&&& {&& if (i,j)为出口
&&&&&&& {&& 将(i,j)加入Path中;
&&&&&&&&&&& 输出Path中的路径;
&&&&&&& else if (i,j)方块可走
&&&&&&& {&& 将(i,j)加入Path中;
&&&&&&&&&&& mgpath(i,j,x2,y2,d+1); //递归调用
&&& mg[x1][y1]=0;&&& &&&&&&&& //未找到(x1,y1)的可走相邻方块时恢复(x1,y1)为可走的
对应的递归算法如下。
int num=1;&&&&&&&&&&&&&&&&&&&&&&&&&&& && //用于路径条数累计
{&&&&&&&&&&&&&&&&&&&&&&&&&&&&& && //当前方块的行号
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& && //当前方块的列号
} Path[MaxSize];&&&&&&&&&&&&&&&&&& //定义存放路径数组
void mgpath(int x1,int y1,int x2,int y2,int d)&& //路径为:(x1,y1)-&(x2,y2)
{&& int i,j,k;
&&& mg[x1][y1]=-1;
&&& int di=-1;
&&& while (di&4)&&&&&&&&&&&&&&& &&&&&& //找下一个可走方块
&&& {&& di++;
&&&&&&& switch(di)
&&&&&&& case 0:i=x1-1;j=y1;
&&&&&&& case 1:i=x1;j=y1+1;
&&&&&&& case 2:i=x1+1;j=y1;
&&&&&&& case 3:i=x1,j=y1-1;
&&&&&&& if (i==x2 && j==y2)&&&&& &&&&& //找到了出口,输出路径
&&&&&&& {&& printf(&\n迷宫路径%d:\n&,num++);
&&&&&&&&&&& Path[d+1].x=x2;Path[d+1].y=y2;
&&&&&&&&&&& for (k=0;k&=d+1;k++)
&&&&&&&&&&& {&& printf(&\t(%d,%d)&,Path[k].x,Path[k].y);
&&&&&&&&&&&&&&& if ((k+1)%5==0)
&&&&&&&&&&&&&&&&&&& printf(&\n&); &&&&& //每输出5个方块后换一行
&&&&&&&&&&& }
&&&&&&&&&&& printf(&\n&);
&&&&&&& else
&&&&&&& {&& if (mg[i][j]==0)&&&&&& &&& //(i,j)可走
&&&&&&&&&&& {&& Path[d+1].x=i;Path[d+1].y=j;
&&&&&&&&&&&&&&& mgpath(i,j,x2,y2,d+1); //递归调用
&&&&&&&&&&& }
&&& mg[x1][y1]=0;&&&&&&&&&&&&&&&& &&&&& //未找到相邻可走方块时回溯
递归算法设计是数据结构中最难的部分之一，很难总结出统一的步骤，读者必须多做练习才能体会递归的实质。
4. 递归算法到非递归算法的转换
递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法分析问题的方法是十分有效的；二是递归算法的时间效率通常比较差。因此，对求解某些问题时，我们希望用递归算法分析问题，用非递归算法具体求解问题。采用手工方法把递归算法转换为非递归算法时主要有如下两种方法：
l&&&&&&&& 对于尾递归和单向递归的算法，可用循环结构的算法替代。
l&&&&&&&& 利用栈模拟系统的运行，通过分析只保存必要的信息，从而用非递归算法替代递归算法。
（1）用循环消除尾递归和单向递归
尾递归是指递归调用语句只有一个而且是处于算法的末尾。例如，前面求n!的算法就是尾递归算法，分析该算法可以发现，当递归调用返回时，返回到上一层再递归调用的下一语句，而这个返回位置正好是算法的末尾。也就是说，以前每次递归调用时保存的返回地址、函数返回值和函数参数等实际上在这里根本就没有被使用。因此，对于尾递归形式的递归算法，不必利用系统运行时的栈保存各种信息。尾递归形式的算法实际上可变成循环结构的算法。循环结构的阶乘问题算法fun(n)如下：
int fun(int n)
{&& int f=1,i;
&&& for (i=2;i&=n;i++)
&&&&&&& f=f*n;
&&& return(f);
尾递归是单向递归的特例。单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，与相互之间的参数无关。例如，求Fibonacci数列的递归模型如下：
f(n)=f(n-1)+f(n-2)&&&&&&& 当n&3
其中，递归调用f(n-1)和f(n-2)只和主调用f(n)有关，与前两个递归调用之间的参数无关，所以求Fibonacci数列属于单向递归。采用循环结构求解Fibonacci数列的算法如下。
int Fib(int n)
{&& int i,f1,f2,f3;
&&& if (n==1 || n==2)
&&&&&& &return(n);
&&& f1=1;f2=2;
&&& for (i=3;i&=n;i++)
&&& {&& f3=f1+f2;
&&&&&&& f1=f2;
&&&&&&& f2=f3;
&&& return(f3);
实际上，采用循环结构消除递归没有通用的转换算法，对于具体问题要深入分析对应的递归结构，设计有效的循环语句进行递归到非递归的转换。
（2）利用栈消除递归
对于不属于尾递归和单向递归的递归算法，需要利用栈转化为与之等价的非递归算法。其基本思路是使用栈保存中间结果。
仍以前面求n!的递归算法进行讨论，其递归模型有一个递归出口和一个递归体两个式子，分别称为(1)式和(2)式。设计一个栈，其结构如下：
&&& struct
&&& {&&&&&&&&&&&&& &&&&&&& //保存n值
&&&&&&&&&&&&&&&&&& &&&&&&& //保存fun1(n)值
&&&&&&&&&&&&&& &&&&&&&&&& //标识是否求出fun1(n)值,1:未求出,0:已求出
&&& } St[MaxSize];&&&&&&& &&& //定义栈
&&& int top=-1;&&&&&&&&&&& &&&&&&& //栈顶指针
计算fun(5)之值的过程如下：
将(5,*,1)进栈;
while (栈不空)
{&& if (栈顶元素未计算出vf值，即St[top].tag==1)
&&& {&& if (栈顶元素满足(1)式)&& && //栈顶元素满足(1)式
&&&&&&& &&&&求出对应的St[top].vf值,并置St[top].tag=0，表示已求出对应的函数值;
&&& &&&&else&&&&&&&&&&&&&&&& &&&&&& //栈顶元素满足(2)式
&&&&&&& &&&&将(St[top].vn-1,*,1)进栈;
&&& else if (栈顶元素已计算出vf值，即St[top].tag==0)
&&& &&&&显然栈顶元素由次栈顶元素通过(2)式分解得到,由栈顶元素的vf值计算出次
&&&&&&& 栈顶元素的vf值并退栈;
&&& if (栈中只有一个已求出vf值的元素)
&&&&&&& 退出循环;
St[0].vf即为所求的fun1(n)值;
对应的fun1算法如下。
int fun1(int n)
{&& top++;&&&&&&&&&&&&&& &&&&&&&&& //初值进栈
&&& St[top].vn=n;
&&& St[top].tag=1;&&&&&&&&&&&& &&& //表示fun1(n)未求出值
&&& while (top&-1)&&&&&&&&&&&&& && //栈不空时循环
&&& {&& if (St[top].tag==1)&&& && //未计算出栈顶元素的vf值
&&&&&&& {&& if (St[top].vn==1)&&& //满足(1)式
&&&&&&&&&&& {&& St[top].vf=1;& &&& //fun1(1)=1
&&&&& &&&&&&&&&&St[top].tag=0;&& & //表示fun1(1)已求出值
&&&&&&&&&&& }
&&&&&&&&&&& else&&&&&&&&&&&&&&&&&&& //满足(2)式
&&&&&&&&&&& {&& top++;
&&&&&&&&&&&&&&& St[top].vn=St[top-1].vn-1;
&&&&&&&&&&&&&&& St[top].tag=1;&& & //表示fun1()未求出值
&&&&&&&&&&& }
&&&&&&& else if (St[top].tag==0)& //已计算出vf值
&&&&&&& {&& St[top-1].vf=St[top-1].vn*St[top]. //满足(2)式
&&&&&&&&&&& St[top-1].tag=0;
&&&&&&&&&&& top--;
&&&&&&& if (top==0 && St[top].tag==0)//栈中只有一个已求出vf的元素时退出循环
&&&&&&&&&&&
&&& return(St[top].vf);& &&&&&&&&&&&&& //返回求得的结果
上例的递归模型中递归体是一种等值关系，所谓等值关系是指&大问题&结果等于若干&小问题&结果的某种运算值。有些情况下，递归体是一种等价关系，所谓等价关系是指&大问题&求解过程转化为若干&小问题&求解而得到的，它们之间不是值的相等关系而是解的等价关系。例如梵塔问题：设有3个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径各不相同，从小到大依次编号为1、2、&、n的圆盘，现要求将X塔座上的n个圆盘移到塔座Z上并仍按同样顺序叠放，圆盘移动时必须遵守以下规则：每次只能移动一个圆盘；圆盘可以插在X、Y和Z中的任一塔座；任何时候都不能将一个较大的圆盘放在较小的圆盘上。
递归求解梵塔问题的原理是：设hanoi(n,x,y,z)表示将n个圆盘从x通过y移动到z上，则有：
hanoi(n-1,x,z,y);
将第n个圆盘从x移到z;
hanoi(n-1,y,x,z)
hanoi(n,x,y,z)
其递归模型如下：
hanoi(n,x,y,z)：move(n,x,z)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 当n=1时 &&&& (1)
hanoi(n,x,y,z)：hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z) &&&&&& 其他情况&&&&&& (2)
对应的递归算法如下。
void hanoi1(int n,char x,char y,char z)
{&& if (n==1)
&&&&&&& printf(&\t将第%d个盘片从%c移动到%c\n&,n,x,z);
&&& {&& hanoi1(n-1,x,z,y);
&&&&&&& printf(&\t将第%d个盘片从%c移动到%c\n&,n,x,z);
&&&&&&& hanoi1(n-1,y,x,z);
将其转换为非递归算法时，用栈模拟递归算法的执行过程，由于(2)式是等价关系，在分解hanoi(n,x,y,z)时，进栈的顺序与(2)右边部分相反，即先处理hanoi(n-1,y,x,z)，再处理move(n,x,z)，最后处理hanoi(n-1,x,z,y)。设栈结构如下：
{&&&&&&&&& &&&&&&&&&&& //保存n值
&&& char x,y,z;&&& &&&&&&&&&& //保存3个塔座
&&&&&& &&&&&&&&&&&&& //标识是否可直接移动一个盘片,1:未可移,0:不能移
} stack[MaxSize];
int top=-1;
对应的过程如下：
将(n,x,y,z,1)进栈;
while (栈不空)
{&& if (栈顶不可直接移动，即St[top].tag==1)
&&& {&& if (栈顶元素满足(1)式)& //栈顶元素满足(1)式
&&&&&&&&&&& 标识可直接移动，即St[top].tag==0;
&&& &&&&else&&&&&&&&&&&&&& &&&& //栈顶元素满足(2)式
&&&&&&& {&& 退栈;
&&&&&&& &&&&将hanoi(n-1,y,x,z)进栈;
&&&&&&&&&&& 将move(n,x,z)进栈;
&&&&&&&&&&& 将hanoi(n-1,x,z,y)进栈;
&&& else if (栈顶可直接移动，即St[top].tag==0)
&&&&&&& 直接移动盘片;
对应的fun1(n,x,y,z)算法如下。
void hanoi2(int n,char x,char y,char z)
{&& int top=-1,
&&& char a,b,c;
&&& top++;
&&& stack[top].n=n;&&&&&&&&&& &&&& //初值进栈
&&& stack[top].x=x;
&&& stack[top].y=y;
&&& stack[top].z=z;
&&& stack[top].tag=1;
&&& while (top&-1)&&&&&&&&&&&&&& & //栈不空时循环
&&& {&& if (stack[top].tag==1)
&&&&&&& {&& if (stack[top].n==1)& //(1)式
&&&&&&&&&&&&&&& stack[top].tag=0;
&&&&&&&&&&& else&&&&&&&&&&&&&&&&&&& //(2)式
&&&&&&&&&&& {&& a=stack[top].x;b=stack[top].y;c=stack[top].z;
&&&&&&&&&&&&&&& num=stack[top].n;
&&&&&&&&&&&&&&& top--;&&&&&&&&&&& && //退栈hanoi(n,x,y,z)
&&&&&&&&&&&&&&& top++;&&&&&&&&&&&& & //将hanoi(n-1,y,x,z)进栈
&&&&&&&&&&&&&&& stack[top].n=num-1;
&&&&&&&&&&& &&&&stack[top].x=b;
&&&&&&&&&&&&&&& stack[top].y=a;
&&&&&&&&&&&&&&& stack[top].z=c;
&&&&&&&&&&&&&&& stack[top].tag=1;
&&&&&&&&&&&&&&& top++;&&&&&&&&&&& && //将move(n,x,z)进栈
&&&&&&&&&&&&&&& stack[top].n=
&&&&&&&&&&&&&&& stack[top].x=a;
&&&&&&&&&&&&&&& stack[top].z=c;
&&&&&&&&&&&&&&& stack[top].tag=0;
&&&&&&&&&&&&&&& top++;&&&&&&&&&&& && //将hanoi(n-1,x,z,y)进栈
&&&&&&&&&&&&&&& stack[top].n=num-1;
&&&&&&&&&&&&&&& stack[top].x=a;
&&&&&&&&&&&&&&& stack[top].y=c;
&&&&&&&&&&&&&&& stack[top].z=b;
&&&&&&&&&&&&&&& stack[top].tag=1;
&&&&&&&&&&& }
&&&&&&& else if (top&-1 && stack[top].tag==0)
&&&&&&& {&& printf(&\t将第%d个盘片从%c移动到%c\n&,
&&&&&&&&&&&&&&& stack[top].n,stack[top].x,stack[top].z);
&&&&&&&&&&& top--;
递归部分主要掌握递归算法设计方法，在各类考试中较少出现递归到非递归转换的算法设计题。但掌握了这类转换有助于较复杂的递归算法设计。
3.4.2 &例题解析
1. 单项选择题
【例3-4-1】递归模型为f(1)=1，f(n)=f(n-1)+n（n&1），其中递归出口是&&& &&。
A. f(1)=0 &&&&&&&&&&&&&&&&&&& &&&&&& B. f(1)=1&&&&&&&&&&&&&& C. f(0)=1 &&&&&&&&&&&&& &&&&&& D. f(n)=n
答：递归出口是，当n=1时，f(1)=1。本题答案为B。
【例3-4-2】递归模型为f(1)=1，f(n)=f(n-1)+n（n&1），其中递归体是& &&&&。
A. f(1)=0&&&&&& &&&&&&&&&&&&&&&&&&&& B. f(0)=1&&&&&&&&&&&&&& C. f(n)=f(n-1)+n&&& &&&&&& D. f(n)=n
答：递归体反映递归方式。本题答案为C。
【例3-4-3】将递归算法转换成非递归算法时，通常要借助的数据结构是&&&& 。
A. 线性表&&&&&&&&&&&&&&&&&&&&&&&&& B. 栈&&&&&&&&&&&&&&&&&&& C. 队列&&&&&&&&&&&&&&&&&&&&&& D. 树
解：递归算法转换成非递归算法时通常使用栈。本题答案为B。
【例3-4-4】将递归算法转换为非递归算法时，通常使用&&&&& 这种数据结构。
【例3-4-5】将f(n)=1+++&（n&3）转化成递归函数，其递归出口是& ①& ，递归体是& ②&
答：① f(1)=1& ② f(n)=f(n-1)+
【例3-4-6】有如下递归算法：
void print(int w)
&&& if (w!=0)
&&& {&& print(w-1);
&&&&&&& for (i=1;i&=w;i++)
&&&&&&&&&&& printf(&%3d&，w);
&&&&&&& printf(&\n&);
调用语句print(4)的结果是&&&&& 。
答：求解过程为：print(4)Þprint(3)Þprint(2)Þprint(1)Þ输出1Þ输出2 2Þ输出3 3 3Þ输出4 4 4 4。本题答案如下：
&&& 3& 3& 3
&&& 4& 4& 4& 4
【例3-4-7】有如下递归算法：
void reverse(int m)
{&& printf(&%d&,n%10);
&&& if (n/10 != 0)
&&&&&&& reverse(n/10);
调用语句reverse(582)的结果是&&&&& 。
答：reverse()函数将给定的参数逆转。本题答案为：285。
3. 算法设计题
【例3-4-8】②设计一个递归算法求一个数组A中的最大元素。
解：将含有n个元素的数组A分解成{a0,a1,&,am}和{am+1,&,an-1}两个子部分，分别求得各子部分中的最大元素ai和aj，比较ai和aj中的大者，就可以求得整个数组的最大元素。而求解子部分中最大元素的方法与整个部分的相同，即再分别将它们分成两个更小的子部分，如此不断分解，直到表中只有一个元素为止。
设Max(A,i,j)表示求A[i..j]元素的最大值。递归模型如下（其中MAX(x,y)表示返回x和y的较大者）：
Max(A,i,j)=A[i]&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& i=j，表示A中只有一个元素时
Max(A,i,j)=MAX{Max(A,i,m),Max(A,m+1,j)}&& 其他情况，其中m=(i+j)/2
对应的递归算法如下。
ElemType Max(ElemType A[],int i,int j)&&& && //求顺序表A[i..j]中最大元素
{&& ElemType max,max1,max2;
&&& if (i==j)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&& //A中只有一个元素
&&&&&&& max=A[i];
&&& {&& m=(i+j)/2;&&&&&&&&&&&&&&&&&&&&&&&&&&& &&& //m取中
&&&&&&& max1=Max(A,i,m);&&&&&&&&&&&&&&&&&&& &&&& //递归调用1
&&&&&&& max2=Max(A,m+1,j);&&&&&&&&&&&&&&&&&&& && //递归调用2
&&&&&&& max=(max1&max2)?max1:max2;
&&& return(max);
【例3-4-9】④有一个不带表头节点的单链表，其节点类型如下：
typedef struct NodeType
&&& struct NodeType *
设计如下递归算法：
（1）求以h为首指针的单链表的节点个数。
（2）正向显示以h为首指针的单链表的所有节点值。
（3）反向显示以h为首指针的单链表的所有节点值。
（4）删除以h为首指针的单链表中值为x的第一个节点。
（5）删除以h为首指针的单链表中值为x的所有节点。
（6）输出以h为首指针的单链表中最大节点值。
（7）输出以h为首指针的单链表中最小节点值。
（8）删除并释放以h为首指针的单链表中所有节点。
解：设h为不带头节点的单链表（含n个节点），如图3.17所示，h-&next也是一个不带头节点的单链表（含n-1个节点），两者除了相差一个节点外，其他都是相似的。
图3.17 不带头节点的单链表
（1）设count(h)用于计算单链表h的节点个数。其递归模型如下：
count(h)=0&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&& h=NULL
count(h)=1+count(h-&next)&& &&&&&&&&&&&&& 其他情况
对应的递归算法如下。
int count(NodeType *h)
{&& if (h==NULL)
&&&&&&& return 0;
&&&&&&& return(1+count(h-&next));
（2）设traverse(h)用于正向扫描单链表h。其递归模型如下：
traverse(h) & 不做任何事情 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& h=NULL
traverse(h) & 输出*h节点之值; traverse(h-&next);&&& 其他情况
对应的递归算法如下。
void traverse(NodeType *h)
{&& if (h!=NULL)
&&& {&& printf(&%d &,h-&data);
&&&&&&& traverse(h-&next);
（3）设revtraverse(h)用于反向扫描单链表h。其递归模型如下：
revtraverse(h) &不做任何事情&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& h=NULL
revtraverse(h) & revtraverse(h-&next); 输出*h节点之值;& 其他情况
对应的递归算法如下。
void revtraverse(NodeType *h)&& //算法(3)
{&& if (h!=NULL)
&&& {&& revtraverse(h-&next);
&&&&&&& printf(&%d &,h-&data);
（4）设delnode(h,x)用于删除单链表h中第一个值为x的节点。其递归模型如下：
delnode(h,x) & 不做任何事情&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& h=NULL时
delnode(h,x) & 删除*h，即h=h-&返回1&& &&&&&&&&&&&&& &&&&&& h-&data=x时
delnode(h,x) & 在后继节点中删除，即delnode(h-&next,x)&&&& 其他情况
对应的递归算法如下。
void delnode(NodeType *&h,ElemType x)&&& &&& //算法(4)
{&& NodeType *p;
&&& if (h!=NULL)
&&& {&& if (h-&data==x)&&&&&&&&&&&&&&&&&&&&&&& & //若首节点值为x
&&&&&&& {&& p=h;
&&&&&&&&&&& h=h-&
&&&&&&&&&&& free(p);
&&&&&&& else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&& //若首节点值不为x
&&&&&&&&&&& delnode(h-&next,x);
（5）设delall(h,x)用于删除单链表h中所有值为x的节点。其递归模型如下：
delall(h,x) & 不做任何事情&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&& h=NULL时
delall(h,x) & 删除*h，即h=h-&&&&&&&&&&&&&&&&&&&&&&& &&&&&& h-&data=x时
&&&&&&&&&&&&&&&&&& 继续在后继节点中删除，即delall(h,x);
delall(h,x) & 在后继节点中删除，即delall(h-&next,x)&&& 其他情况
对应的递归算法如下。
void delall(NodeType *&h,ElemType x)&&& &&&& //算法(5)
{&& NodeType *p;
&&& if (h!=NULL)
&&& {&& if (h-&data==x)&&&&&&&&&&&&&&&&&&&&&&& & //若首节点值为x
&&&&&&& {&& p=h;
&&&&&&&&&&& h=h-&
&&&&&&&&&&& free(p);
&&&&&&&&&&& delall(h,x);&&&&&&&&&&&&&&&&&&& &&&& //在后继节点递归删除
&&&&&&& else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&& //若首节点值不为x
&&&&&&&&&&& delall(h-&next,x);&&&&&&&&&&&&&&& && //在后继节点递归删除
（6）设maxv(h)用于计算单链表h的最大节点值。其递归模型如下（其中MAX(x,y)表示返回x和y的较大者）：
maxv(h)=h-&data&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& h中只有一个节点时
maxv(h)=MAX{h-&data,maxv(h-&next)}&&& 其他情况
对应的递归算法如下。
ElemType maxv(NodeType *h)
&&& if (h-&next==NULL)&&&&&& &&&&&&&&&&&& //只有一个节点的情况
&&&&&&& return(h-&data);
&&& m=maxv(h-&next);&&&&&&& &&&&&&&&&&&&&&&&& //求后继节点的最大值
&&& if (m&h-&data)
&&&&&&& return h-&
（7）设minv(h)用于计算单链表h的最小节点值。其递归模型如下（其中MIN(x,y)表示返回x和y的较小者）：
minv(h)=h-&data&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& h中只有一个节点时
minv(h)=MIN{h-&data,minv(h-&next)}&&&&& 其他情况
对应的递归算法如下。
ElemType minv(NodeType *h)&&&&&& //算法(7)
&&& if (h-&next==NULL)
&&&&&&& return h-&
&&& m=minv(h-&next);
&&& if (m&h-&data)
&&&&&&& return h-&
（8）设release(h)的功能是删除并释放单链表h中所有节点。其递归模型如下：
release(h) & 不做任何事情&&&&&&&&&&&&&&&&&&&&&&& &&&&&& 当h为空表
release(h) & release(h-&next);释放*h节点&& &&&&&& 其他情况
对应的递归算法如下。
void release(NodeType *h)&&&&&& & //算法(8)
{&& if (h!=NULL)
&&& {&& release(h-&next);
&&&&&&& free(h);&&&&&&&&&&&&&&&&&& //释放*h节点
【例3-4-10】⑤设以字符序列A、B、C、D作为顺序栈st的输入，利用push（进栈）和pop（出栈）操作，输出所有可能的出栈序列并实现整个算法。
解：设A={a1,a2,&,am}是已出栈的序列，B={b1,b2,&,bn}是已进栈的序列（如果栈不空的话），C={c1,c2,&,ck}是尚未进栈的序列，如图3.18所示，描述进栈、出栈的状态由A、C两个序列表示即可（由A、C序列可以确定B序列）。
产生所有出栈序列的过程是：如果所有元素都在A序列中（栈空且C序列中的所有元素处理完），此时产生一种出栈序列。否则从某个进栈、出栈的状态（如图3.18所示的状态，称为初始状态）出发，只有两种操作：
（1）从初始状态出发，将C中某元素（如c1）进栈，此时产生另一种进栈、出栈的状态，从该状态继续进行类似的操作。
（2）从初始状态出发，将C中某元素出栈（如bn），即出栈元素bn并将其添加到A的末尾。此时产生另一种进栈、出栈的状态，从该状态继续进行类似的操作。
图3.18 &进栈、出栈的状态
求解过程如图3.19所示，其中&从该状态继续进行类似的操作&和产生所有出栈序列的过程是相似的，所以可以采用递归算法。
图3.19& 求解过程
其中上述（1）、（2）两步都是从初始状态出发的，所以每步执行后都需要将进栈、出栈的状态恢复成初始状态，如（1）步进栈了一个元素，其后要将该元素出栈以恢复成原来的初始状态，（2）步出栈了一个元素x，其后要将x进栈以恢复成原来的初始状态。
为了算法方便，用数组str[0..total-1]表示一个进栈序列（其中元素个数为total），每个下标对应唯一的元素，所以在进栈、出栈中直接用1～n的下标来表示，只有在最后输出一个出栈序列时还原为字符序列。用a数组表示输出序列，用curp表示a数组中当前元素的位置，st是一个栈，包含存放元素的data数组和栈顶指针top。
前面介绍过，进栈、出栈的状态由A、C两个序列表示即可，A序列中有curp个元素，C序列的当前处理元素设为m（表示C序列为ck&cm），这样进栈、出栈的状态由m、curp唯一确定，设计的处理函数如下：
void process(int m,int a[],int curp)
为了简单，栈运算只设计了基本的处理过程。完整的程序如下：
#include &stdio.h&
#define MaxSize 10
struct stacknode
{&& int data[MaxSize];
}&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& //全局变量，定义顺序栈
int total=4;&&&&&&&&&&&&&&&&&&&&&& &&&& //全局变量，定义输入序列的元素个数
char str[]=&ABCD&;&&&&&&&&&&&&&&&& &&& //全局变量，指定进栈序列
int sum=0; &&&&&&&&&&&&&&&&&&&&&&&&&&&& //全局变量，累计出栈序列个数
void initstack()&&&&&&&&&&&&&&&&&& //初始化顺序栈
&&& st.top=-1;
void push(int n)&&&&&&&&&&&&&&&&&&&&& & //元素n进栈运算
{&& st.top++;
&&& st.data[st.top]=n;
int pop()&&&&&&&&&&&&&&&&&&&&&& &&&&&&& //退栈运算
&&& temp=st.data[st.top];
&&& st.top--;
bool empty()&&&&&&&&&&&&&&&&&&&&&&&& && //判断栈空否运算
{&& if (st.top==-1)
void process(int m,int a[],int curp)//处理C序列中m位置的元素
{&& int x,i;
&&& if (m&total && empty())&&&&&&&&& & //输出一种可能的方案
&&& {&& printf(&& &);
&&&&&&& for (i=0;i&i++)&&&&&&&& & //输出a中的元素序列，构成一种出栈序列
&&&&&&&&&&& printf(&%c &,str[a[i]-1]);
&&&&&&& printf(&\n&);
&&&&&&& sum++;&&&&&&&&&&&&&&&&&&&&&&& && //出栈序列个数增1
&&& if (m&=total)&&&&&&& &&&&&&&&&&&&&& //编号m的元素进栈时递归
&&& {&& push(m);&&&&&&&&&&&&&&&&&&&&& && //m进栈
&&&&&&& process(m+1,a,curp);&&&&&& &&& //递归：从该状态继续进行类似的操作
&&&&&&& pop();&&&&&&&&&&&&&&&&&&&&&&&& & //出栈以恢复环境
&&& if (!empty())&&&&&&& &&&&&&&&&&&&&& //编号m的元素出栈时递归
&&& {&& x=pop();&&& &&&&&&&&&&&&&&&&&&& //出栈x
&&&&&&& a[curp]=x;&&&&&&&&&&&&&&&&&&&& & //将x输出到a中
&&&&&&& curp++;&&&&&&&&&&&&&&&&&&&&&& && //a中元素个数增1
&&&&&&& process(m,a,curp);&&&&&&&&&&& //递归：从该状态继续进行类似的操作
&&&&&&& push(x);&&&&&&&&&&&&&&&&&&&&&& & //进栈以恢复环境
void main()
{&& int a[MaxSize];
&&& initstack();
&&& printf(&所有出栈序列:\n&);
&&& process(1,a,0);&&&&&&&&&&&&&&&&&&& //m从1开始，curp从0开始
&&& printf(&出栈序列个数:%d\n&,sum);
程序的执行结果如下：
所有出栈序列:
出栈序列个数:14
【例3-4-11】④用于列车编组的铁路转轨网络是一种栈结构，如图3.20所示。其中，右边轨道是输入端，左边轨道是输出瑞。当右边轨道上的车皮编号顺序为1、2、3、4时，如果执行操作：进栈、进栈、出栈、进栈、进栈、出栈、出栈、出栈，则在左边轨道上的车皮编号顺序为2、4、3、l。设计一个算法，输入n个整数，表示右边轨道上n节车皮的编号，用上述转轨栈对这些车皮重新编排，使得编号为奇数的车皮都排在编号为偶数的车皮的前面。
图3.20 &铁路转轨网络
本题和以下两题都可以看做铁轨的应用专题，涉及栈、队列和递归等。
解：将转轨栈看成一个栈，将左边轨道看成是一个队列。从键盘逐个输入表示右边轨道上车皮编号的整数，根据其奇偶性做如下处理：若是奇数，则将其插入到表示左边轨道的顺序队列的队尾；若是偶数，则将其插入到表示转轨栈的顺序栈的栈顶。当n个整数都检测完之后，这些整数已全部进入队列或栈中。此时，首先按先进先出的顺序输出队列中的元素，然后再按后进先出的顺序输出栈中的元素。对应的算法如下。
#include &stdio.h&
#define MaxSize 100
void fun1()
{&& int i,n,x;
&&& int Stack[MaxSize],top=-1;&&&&&&&&&&&&&&& &&&& //栈和栈指针
&&& int Queue[MaxSize],front=0,rear=0;&&&&&&& //队列和队指针
&&& printf(&n:&);
&&& scanf(&%d&,&n);
&&& for (i=0;i&n;i++)
&&& {&& printf(&第%d个车皮编号:&,i+1);
&&&&&&& scanf(&%d&,&x);
&&&&&&& if (x%2==1)&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&& //编号为奇数,则进队列
&&&&&&& {&& Queue[rear]=x;
&&&&&&&&&&& printf(&& %d进队\n&,x);
&&&&&&&&&&& rear++;
&&&&&&& else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&& //编号为偶数,则进栈
&&&&&&& {&& top++;
&&&&&&&&&&& Stack[top]=x;
&&&&&&&&&&& printf(&& %d进栈\n&,x);
&&& printf(&出轨操作:\n& &);
&&& while (front!=rear)&&&&&&&&&&&&&&&&&&&&&&& &&&&& //队列中所有元素出队
&&& {&& printf(&%d出队 &,Queue[front]);
&&&&&&& front++;
&&& while (top&=0)&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&& //栈中所有元素出栈
&&& {&& printf(&%d出栈 &,Stack[top]);
&&&&&&& top--;
&&& printf(&\n&);
void main()
&&& fun1();
本程序的一次求解结果如下：
第1个车皮编号:4L& 4进栈
第2个车皮编号:1L& 1进队
第3个车皮编号:3L& 3进队
第4个车皮编号:2L& 4进栈
出轨操作：
　　1出队　3出队　2出栈　4出栈
【例3-4-12】⑤对于如图3.20所示的铁路转轨网络，设计一个算法，求出当右边轨道上n节车皮的编号为1、2、3、&、n顺序排列时，在左边轨道上所有可能得到的车皮编号顺序。
解：左边轨道用顺序队列表示，转轨栈用顺序栈表示。假设在某一时刻，队尾指针为rear，栈顶指针为top，编号为i的车皮来到转轨栈的入口处，这种状态（称为状态X0）有两种可能的处理方法：
l&&&&&&& 输出栈顶元素。其结果是，队列中多了一个元素，栈中少了一个元素，转轨栈入口处的车皮编号仍然是i，这种状态称为状态X1。
l&&&&&&& i进栈。其结果是，队列中元素不变，栈中元素多了一个，转轨栈入口处的车皮编号变成了i+1，这种状态称为状态X2。显然，状态X1、状态X2的处理方法和状态X0的处理方法是相同的，用递归方法处理最简单。
对应的算法如下。
#include &stdio.h&
#define MaxSize 100
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&& //车皮个数
int Stack[MaxSize];&&&&&&&&&&&&&&&&&&&&&&&&&& & //顺序栈
int Queue[MaxSize];&&&&&&&&&& &&&&&&&&&&&&&&&&& //顺序队
void fun2(int rear,int top,int i)&&&&&&&&&& & //处理第i个车皮进入铁轨
&&& if (rear==n)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& && //n个元素已全部入队,输出一个解
&&& {&& printf(&& &);
&&&&&&& for (j=1;j&=n;j++)
&&&&&&&&&&& printf(&%d &,Queue[j]);
&&&&&&& printf(&\n&);
&&& {&& if (top&-1)&&&&&&&&&&&&&&&&&&&&&&&&&& && //栈不空
&&&&&&& {&& rear++;
&&&&&&&&&&& Queue[rear]=Stack[top];&&&&&&&& &&& //出栈一个元素并将其入列
&&&&&&&&&&& top--;
&&&&&&&&&&& fun2(rear,top,i);&&&&&&&&&&&&&&& &&& //递归处理X1状态
&&&&&&&&&&& top++;&&&& &&&&&&&&&&&&&&&&&&&&&&&&&& //恢复处理前的状态
&&&&&&&&&&& Stack[top]=Queue[rear];&&&&&&&&&&&&&&&
&&&&&&&&&&& rear--;
&&&&&&& if (i&=n)&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&& //转轨栈右边还有未处理车皮
&&&&&&& {&& top++;&&&&&&&&&&&&&&&&&&&&&&&&&&& &&& //编号为i的车皮进栈
&&&&&&&&&&& Stack[top]=i;
&&&&&&&&&&& fun2(rear,top,i+1);&&&&&&&&&&& &&& //递归处理X2状态
void main()
{&& printf(&车皮个数n:&);
&&& scanf(&%d&,&n);
&&& printf(&所有可能的车皮顺序:\n&);
&&& fun2(0,-1,1);
本程序的一次求解结果如下：
车皮个数n:4L
所有可能的车皮顺序：
本题的解法与【例3-4-10】算法相似。
【例3-4-13】④对于如图3.20所示的铁路转轨网络，假设右边轨道上n节车皮的编号序列为A，左边轨道上n节车皮的编号序列为B。设计一个算法，判断序列B是不是借助转轨栈由序列A得到的。
解：将右边轨道上车皮编号序列存入数组a中，左边轨道上车皮编号序列存入数组b中，令i、j的初始值均为0，即分别指向a、b数组的第一个元素。反复执行下列操作：比较栈顶元素Stack[top]和b[j]的大小，若两者不相等，则将a[i]进栈，i加1；否则出栈栈顶元素，j加1。当i大于等于n或j大于等于n时，上述循环过程结束。如果序列B是由序列A得到的，则此时必有j&n。对应的算法如下。
#include &stdio.h&
#define MaxSize 100
int fun3(int a[],int b[],int n)
{&& int i=0,j=0;&&&&&&&&&&&&&&&&&&&&&&& &&& //i,j分别为a[]和b[]的下标
&&& int Stack[MaxSize],top=-1;
&&& {&& if (top==-1 || Stack[top]!=b[j])& //栈为空或栈顶不为b[j]
&&&&&&& {&& top++;&&&&&&&&&&&&&&&&&&&&&&&&& & //a[i]进栈
&&&&&&&&&&& Stack[top]=a[i];&&&
&&&&&&&&&&& i++;
&&&&&&& else
&&&&&&& {&& top--;&&&&&&&&&&&&& &&&&&&&&&&&&& //出栈一次
&&&&&&&&&&& j++;&&&&&&&&&&&&&&&&&&&&&&&&&&& & //j指向b[]的下一个元素
&&& } while (i&n && j&n);
&&& while (Stack[top]==b[j])&&&&&&&&&&& && //若栈顶元素等于b[j]
&&& {&& top--;&&&&&&&&&&&&&&&&&&&&&&&&&&&& && //出栈一次
&&&&&&& j++;&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&& //j指向b[]的下一个元素
&&& if (j&=n) return 1;
&&& else return 0;
void main()
{&& int i,n;
&&& int a[MaxSize],b[MaxSize];
&&& printf(&车皮个数n:&);
&&& scanf(&%d&,&n);
&&& printf(&右边轨道上车皮编号序列:&);
&&& for (i=0;i&n;i++)
&&&&&&& scanf(&%d&,&a[i]);
&&& printf(&左边轨道上车皮编号序列:&);
&&& for (i=0;i&n;i++)
&&&&&&& scanf(&%d&,&b[i]);
&&& if (fun3(a,b,n)==1)
&&&&&&& printf(&由A可能得到B\n&);
&&&&&&& printf(&由A不可能得到B\n&);
本程序的一次求解结果如下：
车皮个数n:4L
右边轨道上车皮编号序列：1 2 3 4L
左边轨道上车皮编号序列：4 1 2 3L
由A不可能得到B
【例3-4-14】⑤设计一个递归算法求n个不同字符的所有全排列。
解法1：设str是含n个不同字符的字符串，perm(str,k,n)为str[k..n-1]的所有字符的全排序，perm(str,k+1,n)为str[k+1..n-1]的所有字符的全排序，如图3.21所示，perm(str,k+1,n)处理的字符个数比perm(str,k,n)处理的字符个数少1，前者为&小问题&，后者为&大问题&。假设perm(str,k+1,n)可求，对于str[k]位置，可以取str[k+1..n-1]任何位置的元素，再组合perm(str,k+1,n)得到perm(str,k,n)。递归模型如下：
perm(str,k,n) & 输出str&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&& 当k=n-1时，即只对一个
字符求全排列
perm(str,k,n) & str[k]位置取str[k]～str[n-1]任何&&&&&&&&&&& &&&&&& 其他情况
&&&&&&&&&&&&&&&&&&&& &位置的元素，并组合perm(str,k+1,n)的结果
图3.21 &求str的全排列
例如，求123的全排列如图3.22所示。
图3.22 &递归求123全排列的过程
为了让str[k]位置取str[k..n-1]任何位置的元素，可将str[k]与str[k..n-1]进行交换。对应的递归算法如下。
void perm(char str[],int k,int n)
{&& int i,j;
&&& if (k==n-1)&&&&&&&&&&&&&&&&&& & //输出str
&&& {&& for (j=0;j&n;j++)
&&&&&&&&&&& printf(&%c&,str[j]);
&&&&&&& printf(&\n&);
&&& {&& for (i=k;i&n;i++)
&&&&&&& {&& tmp=str[k];&&&&&&&&&& & //str[k]&str[i]
&&&&&&&&&&& str[k]=str[i];
&&&&&&&&&&& str[i]=
&&&&&&&&&&& perm(str,k+1,n);
&&&&&&&&&&& tmp=str[i];&&&&&&&&&& & //str[k]&str[i]
&&&&&&&&&&& str[i]=str[k];
&&&&&&&&&&& str[k]=
解法2：设str是含n个不同字符的字符串，perm(str,k-1,n)为str[0..k-1]的所有字符的全排序，perm(str,k,n)为str[0..k]的所有字符的全排序，如图3.23所示，perm(str,k-1,n)处理的字符个数比perm(str,k,n)处理的字符个数少1，前者为&小问题&，后者为&大问题&。假设perm(str,k-1,n)可求，对于str[k]位置，可以取str[0..k]任何位置元素，再组合perm(str,k-1,n)，则得到perm(str,k,n)。递归模型如下：
perm(str,k,n) & 输出str&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&& 当k=0时，即只对一个字符求全排列
perm(str,k,n) & str[k]位置取str[0..k]任何位置元素,&& 其他情况
&&&&&&&&&&&&&&&&&&&& 并组合perm(str,k-1,n)的结果
图3.23 &求str的全排列
为了让str[k]位置取str[0..k]任何位置的元素，可将str[k]与str[0..k]进行交换。对应的递归算法如下。
void perm1(char str[],int k,int n)
{&& int i,j;
&&& if (k==0)&&&&&&&&&&&&&&& &&&&& //输出str
&&& {&& for (j=0;j&n;j++)
&&&&&&&&&&& printf(&%c&,str[j]);
&&&&&&& printf(&\n&);
&&& {&& for (i=0;i&=k;i++)
&&&&&&& {&& tmp=str[k];&&&&&&& //str[k]&str[i]
&&&&&&&&&&& str[k]=str[i];
&&&&&&&&&&& str[i]=
&&&&&&&&&&& perm1(str,k-1,n);
&&&&&&&&&&& tmp=str[i];&&&&&&& &&& //str[k]&str[i]
&&&&&&&&&&& str[i]=str[k];
&&&&&&&&&&& str[k]=
【例3-4-15】⑤设计一个递归算法求解组合问题：从自然数1、2、&、m中任取k个数的所有组合。
解：设comb(m,k)为从1～m中任取k个数的所有组合。当组合的第1个数字选定后，其后的数字是从余下的m-1个数中取k-1个数的组合，即comb(m-1,k-1)，comb(m,k)为&大问题&，comb(m-1,k-1)为&小问题&。
采用a数组保存组合结果，由于每个组合不考虑次序，为了简便，不妨设定结果按照递增排列，如求得1、2、3中的两个数的所有组合为：12、13、23。先确定a中最后一个元素的取值，对于a[k-1]只能取m～k中的一个值i（这样a[0..k-2]的取值均小于i），如图3.24所示，再组合comb(i-1,k-1)的结果便得到了一个组合，如1、2、3中的2个数的所有组合的过程如图3.25所示。其递归模型如下：
comb(m,k) & 输出一个解&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 当k=1时
comb(m,k) & a[k-1]位置取m～k的任何值i&&&&&&&&&& 其他情况
&&&&&&&&&&&&&&&&&&&& 并组合comb(i-1,k-1)的结果
&&&&&&&&&&&& 图3.24& 求组合问题&&&&&&&&&&&&&&&&&&&&&& 图3.25& 求comb(3,2)的过程
对应的完整程序如下：
#include &stdio.h&
#define MaxSize 10
int m,k;&&&&&&&&&&&&&&&&&&& &&&&&& //全局变量
void print(int a[])&&&&&&& &&&&&& //输出一个组合
&&& printf(&&& &);
&&& for (j=0;j&=k-1;j++)
&&&&&&& printf(&%d &,a[j]);
&&& printf(&\n&);
void comb(int a[],int m,int k)
&&& for (i=m;i&=k;i--)
&&& {&& a[k-1]=i;&&&&&&&&&&& &&&&& //确定a[k-1]位置的取值
&&&&&&& if (k&1)&&&&&&&&&&&&&&& &&& //递归调用
&&& &&&&&&&&comb(a,i-1,k-1);
&&& &&&&else&&&&&&&&&&&&&&&&&&& &&&& //k=1时输出一个组合
&&& &&&&&&&&print(a);
void main()
{&& int a[MaxSize];
&&& m=5; k=3;
&&& printf(&1..%d中%d个的组合结果如下:\n&,m,k);
&&& comb(a,m,k);
&&& printf(&\n&);
本程序的执行结果如下：
1..5中3个的组合结果如下：
【例3-4-16】⑤采用递归算法求解皇后问题：在n&n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线，并编写完整的程序。
解：对于n皇后问题，每一行只能放一个皇后，用(k,q[k])（1&k&n）表示皇后的位置。设place(k,n)表示已在前面放置好了第1～k-1个皇后（共放置好了k-1个皇后），用于放置第k～n个皇后（还有n-k+1个皇后需放置），则place(k+1,n)表示需要放置第k+1～n个皇后（需放置n-k个皇后），所以place(k,n)是&大问题&，place(k+1,n)是&小问题&。假设place(k+1,n)可求，则place(k,n)就是要在第k行上放置一个皇后，再调用place(k+1,n)。求解皇后问题的递归模型如下：
place(k,n) & n个皇后放置完毕，输出一个解&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 若k=n
place(k,n) & 对于第k行的每个合适的列号j，在其上放置一个皇后;& 其他情况
&&&&&&&&&&&&&&&&&&&& place(k+1,n);
得到递归过程如下：
place(int k,int n)
{&& if (k==n)
&&&&&&& 输出一个解;
&&&&&&& for (int j=1;j&=n;j++)&&&&&& & //在第k行上穷举每个列j
&&&&&&&&&&& if (第k行的第j列合适)
&&&&&&&&&&& {&& 在该位置处放一个皇后，即q[k]=j
&&&&&&&&&&& &&&&place(k+1,n);
&&&&&&&&&&& }
对应的完整程序如下：
#include &stdio.h&
const int N=20;&&&&&&&&&&&&&&&&&&& //最多的皇后个数
int q[N];&&&&&&& &&&&&&&&&&&&&&&&&&&&&& //存放各皇后所在的列号
int cont=0;&&&&&&&&&&&&&&&&&&&&&&& &&&& //存放解个数
int abs(int i)&&&&&&&&&&&&&&&&&&& &&&& //求绝对值
{&& if (i&0) return -i;
void print(int n)&&&&&&&&&&&&&&& &&&&& //输出一个解
&&& cont++;
&&& printf(&& 第%d个解:&,cont);
&&& for (i=1;i&=n;i++)&&&&&&&&& &&&&&& //(i,q[i])位置有一个皇后
&&&&&&& printf(&(%d,%d) &,i,q[i]);
&&& printf(&\n&);
int find(int j,int k)&&&&&&&&&&& &&&& //测试(k,j)能否放皇后
&&& for (i=1;i&k;i++)&&&&&&&&&&&&&&& & //i=1～k-1各行已放置了皇后
&&&&&&& if ((q[i]==j)&&&&&&& &&&&&&&&&& //判断是否同列
&&&&&&&&&&& || (abs(q[i]-j)==abs(i-k)))&& //(i,q[i])与(k,j)是否同对角线
&&&&&&&&&&& return 0;&&&&&&&&&&&&&&& &&& //返回0,表示(k,j)不能放皇后
&&& return 1;
void place(int k,int n)&&&&&&&&&&& && //从放第k个皇后开始求解
{&& if (k&n) &&&&&&&&&&&&&&&&&&&&&&&&&& //所有皇后放置结束
&& &&&&&print(n);&&&&&&&&&&&&&&&&&&& &&& //输出一个解
&&&&&&& for (int j=1;j&=n;j++)&&& //在第k行上穷举每个列号j
&&&&&&&&&&& if (find(j,k))
&&&&&&&&&&& {&& q[k]=j;&&&&&&&&&&&&& &&& //在(k,q[k])处放一个皇后
&&&&&&&&&&&&&&& place(k+1,n);&&&&&&& && //递归调用放余下的皇后
&&&&&&&&&&& }
void main()
&&& place(1,4);
利用上述程序求解4皇后的结果如下：
第1个解：(1,2) (2,4) (3,1) (4,3)
第2个解：(1,3) (2,1) (3,4) (4,2)
【例3-4-17】⑤akm函数的定义如下：
&&&&&&&&&&&&&&&&&&&&&&&&&&& n+1 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& m=0&&&&&&&&&&&&&& (1)
akm(m,n)=&&&& akm(m-1,1)&&&&&&&&&&&&&&&&&&&&&&&& m&0, n=0&&&&& (2)
&&&&&&&&&&&&&&&&&&&& akm(m-1,akm(m,n-1))&&&&&&&& m&0, n&0&&& (3)
设计对应的递归和非递归算法。
对应的递归算法如下。
int akm1(int m,int n)
&&& if (m==0)
&&&&&&& return(n+1);
&&& else if (n==0)
&&&&&&& return akm1(m-1,1);
&&& {&& g=akm1(m,n-1);
&&&&&&& return(akm1(m-1,g));
对应的非递归算法如下。
int akm2(int m,int n)
{&& struct
&&& {&& int vm,&&&&&&&&&&& &&&&& //分别保存m和n值
&&&&&&&&&&&&&&&&&&&&&&&&&& & //保存akm(m,n)值
&&&&&&&&&&&&&&&&&&&&&& &&& //标识是否求出akm(m,n)值,1:未求出,0:已求出
&&& } St[MaxSize];&&&&&&&&&&&&&&& //定义栈
&&& int top=-1;&&&&&&&&&&&&&&&&&&& //栈顶指针
&&& top++;&&&&&&&&&&&&&&&&&&&&&&& && //初值进栈
&&& St[top].vm=m;St[top].vn=n;St[top].tag=1;
&&& while (top&-1)&&&&&&&&&&&&&&& //栈不空时循环
&&& {&& if (St[top].tag==1)&&& && //未计算出栈顶元素的vf值
&&&&&&& {&& if (St[top].vm==0)&& & //(1)式
&&&&&&&&&&& {&& St[top].vf=St[top].vn+1;
&&&&&&&&&&&&&&& St[top].tag=0;
&&&&&&& &&&&}
&&&&&&&&&&& else if (St[top].vn==0)//(2)式
&&&&&&&&&&& {&& top++;
&&&&&&&&&&&&&&& St[top].vm=St[top-1].vm-1;
&&&&&&&&&&&&&&& St[top].vn=1;
&&&&&&&&&&&&&&& St[top].tag=1;
&&&&&&&&&&& }
&&&&&&&&&&& else&&&&&&&&&&&&&&&&&&& //(3)式
&&&&&&&&&&& {&& top++;
&&&&&&&&&&&&&&& St[top].vm=St[top-1].
&&&&&&&&&&&&&&& St[top].vn=St[top-1].vn-1;
&&&&&&&&&&&&&&& St[top].tag=1;
&&&&&&&&&&& }
&&&&&&& else if (St[top].tag==0)& //已计算出vf值
&&&&&&& {&& if (top&0 && St[top-1].vn==0)&& && //(2)式
&&&&&&&&&&& {&& St[top-1].vf=St[top].
&&&&&&&&&&&&&&& St[top-1].tag=0;
&&&&&&&&&&&&&&& top--;
&&&&&&&&&&& }
&&&&&&&&&&& else if (top&0)&&&&& & //(3)式
&&&&&&&&&&& {&& St[top-1].vm=St[top-1].vm-1;
&&&&&&&&&&&&&&& St[top-1].vn=St[top].
&&&&&&&&&&&&&&& St[top-1].tag=1;
&&&&&& &&&&&&&&&top--;
&&&&&&&&&&& }
&&&&&&& if (top==0 && St[top].tag==0)//栈中只有一个已求出vf的元素时退出循环
&&&&&&&&&&&
&&& return St[top].
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'}