本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第3.3节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.3栈与递归实现
3.3.1递归的定义
栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称为递归函数。其中直接调用自己的函数称为直接递归。间接调用自己的函数称为间接递归。
递归是算法设计中最重要的手段。它通常把一个大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解。下面是常见的使用递归的三种情况。
(1)定义是递归的
现实中，有许多定义是递归定义的，以n!为例来说明，其定义如下：
fact(n)=1n=0//递归终止条件
n*fact(n－1)n>0//递归步骤
其递归算法如下：
int fact(int n){
if(n==0)return 1;
else return(n*fact(n-1));
}
(2)数据结构是递归的
某些数据结构就是递归的，则它们的操作可递归地描述。例如，单链表就是一种递归的数据结构，单链表的结点Lnode的定义由data和next组成；而指针next则由Lnode定义。
对于递归定义的数据结构，采用递归的方法编写算法十分方便。例如，使用递归查找非空不带头结点单链表中的最后一个结点的算法可描述如下：
void FindLastElem(LinkList L){
if(L->next==NULL)printf(L->data);
else FindLastElem(L->next);
}
(3)问题的解法是递归的
某些问题本身没有明显的递归结构，但也用递归来求，甚至有些问题只能用递归求解。一个典型的例子就是Hanoi塔问题。
3.3.2递归与栈的关系
在用高级语言编写的程序中，调用函数和被调用函数之间的链接和信息交换需通过栈来进行。
通常，当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，系统需先完成三项任务：1)将所有的实参、返回地址等信息传递给被调用函数保存；2)为被调用函数的局部变量分配存储区；3)将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，系统也应完成下列三项任务：1)保存被调用函数的计算结果；2)释放被调用函数的数据区；3)依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过栈来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区；每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。
假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即第i+1层。反之，退出第i层返回至上一层，即第i-1层。为了保证递归函数正确执行，系统需要一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层所需信息构成一个“工作记录”，其中包括所有的实参、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个工作记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
3.3.3递归的实现
下面以汉诺（Hanoi）塔问题来说明递归的实现。
假设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小不同、依次从小到大编号为1，2，…，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排。移动过程中一次只能移动一个圆盘，不允许大圆盘放在小圆盘上面，而只能借助于中间的塔座。
如何实现移动圆盘的操作呢？当n=1时，只要将编号为1的圆盘直接从X移至Z上即可；当n>1时，可以先将编号为n的圆盘之上的n-1个圆盘借助于Z移至Y上，再把编号为n的圆盘移至Z上，最后再将Y上的n-1个圆盘借助X移至Z上。显然，这个过程是递归的。其递归算法如下：
void hanoi(int n,char x,char y,char z) //将塔座x上按直径由小到大且自上而下编号为1至n的n个
//圆盘按规则搬到塔座z上,y可用作辅助塔座
1{
2if(n==1)
3move(x,1,z);//将编号为1的圆盘从x移到z
4else{
5hanoi(n-1,x,z,y);//将x上编号为1至n-1的圆盘移到y,z作辅助塔
6move(x,n,z);//将编号为n的圆盘从x移到z
7hanoi(n-1,y,x,z);//将y上编号为1至n-1的圆盘移到z,x作辅助塔
8}
9}
其中move定义如下：
void move(char x,int n,char z){
printf("%d号圆盘:%c---->%c\n",n,x,z);
}
3.3.4用递归求所有出栈序列
当序列1，2，…，n依次入栈，请问如何求出其所有可能的出栈序列？下面给出求所有出栈序列的递归算法的描述及算法：
1)若n=1，则写下唯一的出栈序列。
2)否则，递归调用该算法求出第一个元素1作为第k个元素的所有出栈序列(k=1，2，…，n)。
求所有出栈序列的递归求解算法如下：
int count=0;//记录出栈序列数
char a［7］,b［10000］［7］;//数组a存储输入序列(为了实现简单，这里假定每个元素是一位整数或一个字
//符)，数组b存储得到的所有出栈序列
void perm(char a［］,int k,int n){//k为数组a中的第一个元素的下标,n为数组a中的最后一个元素的下标
int i,j,s,flag;
char temp,t［7］;
strcpy(t,a);
if(k==n){
s=0; flag=0;
while((!flag)&&(strcmp(b［s］,"\\ 0")))if(!strcmp(a,b［s++］))flag=1; //检验是否与已有出栈
//序列重复。若不重复，
//则输出出栈序列
if(!flag){strcpy(b［s］,a);count++;printf("%d:%s\\n",count,a);}
}
else
for(i=k;i<=n;i++){//依次求出第一个元素在第k位的所有出栈序列
strcpy(a,t);temp=a［k］;
for(j=k;ja［i］=temp;
perm(a,k,i-1);
perm(a,i+1,n);
}
}
335递归的消除
通过上面的例子可以看出，递归既是强有力的数学方法，也是程序设计中一个很有用的工具。其特点是对递归问题描述简洁，结构清晰，程序的正确性容易证明。然而，有时需考虑怎样将一个递归算法换成等价的非递归算法，这称为“递归消除”。研究递归消除的主要原因有以下两个方面：第一，递归消除有利于提高算法的时空性能。在一般情况下，递归算法的时空性能相对较差，而非递归算法的时空性能要高得多。第二，研究递归消除有助于透彻理解递归机制，而这种理解是熟练掌握递归程序设计技能的必要前提。
根据是否需要引入工作栈作为控制机构，可将递归消除技术分成两类，下面分别加以讨论。
1简单递归消除(尾递归和单向递归消除)
简单递归是尾递归和单向递归。其中，尾递归是指递归调用语句只有一个，而且是处于算法的最后；单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，这些递归调用语句相互之间参数无关，并且这些递归调用语句也和尾递归一样处于算法的最后。这类递归算法可以不使用工作栈作为控制机构而直接转换成循环算法。
尾递归的一个典型例子是计算阶乘n!的递归算法，将其转换成非递归算法如下：
int fact(int n){
int y=1;//计算0！
for(int i=1;i<=n;i++)//依次计算1!,…,n!
y=yi;//i!=(i―1)!i
return y;
}
单向递归的一个典型例子是计算斐波那契数列。斐波那契数列是指：数列中的每一项都等于前两项之和，它的前几项为1，1，2，3，5等。其递归算法Fib(n)如下：
fib(int n){
if(n==0||n==1)return n;//递归出口
else return fib(n-1)+fib(n-2);//递归调用
}
将其转换成非递归算法如下：
int fib(int n){
int x,y,z;
if(n==0||n==1)return n;//计算fib(0)、fib(1)
else{
int x=0,y=1,z;//x=fib(0)，y=fib(1)
for ( i=2;i<= n; i++){
z=y;//z=fib(i-1)
y=x+y;//y=fib(i-1)+fib(i-2),求fib(i)形成第i项
x=z
};//x=Fib(i-1)
}
return y;
}
}
2基于栈的递归消除
在复杂情况下，一个递归算法无法直接转换成循环算法。例如，前面介绍的汉诺塔问题。在这种情况下，通常通过引入一个工作栈保存“返回位置”以实现过程调用的返回。基于栈消除递归必须遵循以下规则：
1)在过程(或函数)的开始部分，插入声明为栈的代码并将其初始化为空，在一般情况下，这个栈用来存放参数、局部变量和函数的值，每次递归调用的返回地址也要存入栈。
2)将标号L1附于第一条可执行语句。然后，对于每一处递归调用用一组执行规则3）~规则7）的指令来代替。
3)将所有参数和局部变量的值存入栈，栈顶指针可作为一个全程变量来看待。
4)建立第i个新标号Li，并将i存入栈，这个标号的i值将用来计算返回地址。此标号放在规则 7 所描述的程序段中。
5)计算这次调用的各实参(它们可能是表达式)的值，并把这些值赋给相应的形参。
6)插入一条无条件转移语句转向过程(或函数)的开始部分。
7)如果这个过程是函数，则对于这个递归过程中含有此次函数调用的那条语句作如下处理：对该语句的此次函数调用部分用从栈顶取回该函数值的代码代替，其余部分的代码按原描述方式照抄，并将规则4）中建立的标号附于这条语句。如果此过程不是函数，则将规则4）中建立的标号附在规则6）所产生的转移语句后面的那条语句。
以上规则是为了消除过程中的多处递归调用，现在对递归过程中出现的return进行处理(纯过程结束的地方可看成是一条没有值与其相联系的return语句)，在每个return语句的地方，执行下述规则：
8)如果栈为空，则执行正常返回，否则执行规则9)。
9)将所有输出参数的当前值赋给栈顶上的那些对应变量。
10)如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标值赋给一个未使用的变量。
11)从栈中退出所有局部变量和参数的值，并把它们赋给对应的变量。
12)如果这个过程是函数，则插入用来计算紧接在return后面的表达式的指令，并将结果值存入栈顶。
13)用返回地址标号的下标实现对该标号语句的转向。
在一般情况下，使用上述规则都可将一个直接递归过程正确地翻译成与之等价的非递归过程。下面考察一个递归转化的例子。求数组A［n］中最大的元素，其递归算法描述如下：
int max1(int i)
{//函数返回A［n］中最大元素的下标，其中A［n］和n均为全局变量
int j,k;
if(ij=max(i+1);
if(A［i］>A［j］)k=i;
else k=j;
}
else k=n-1;
return k;
}
利用上述规则将其转化为非递归算法如下：
int max2(int i){
int j,k,addr;
SqStack S;
InitStack(S);//规则1)，构造一个顺序栈
L1:if(i{ Push(S,2);//规则4)
Push(S,i);//规则3)
i++;//规则5)
goto L1;//规则6)
}//if
else k=n-1;
L2:Pop(S,j);//规则7)
if(A［i］>A［j］)k=i;
else k=j;
if(StackEmpty(S))return k;//规则8)
else{
Pop(S,addr);//规则10)
Pop(S,i);//规则11)
Push(S,k);//规则12)
if(addr==2)goto L2;//规则13)
}//else
}
需要说明的是，不必在任何情况下都完全照搬前面的13条规则，而要具体问题具体分析。
