🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：栈有一个重要应用是在程序设计语言中实现递归，它通常把一个大型复杂问题的描述和求解变得简洁和清晰。因此递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归方法更加合适。本节将介绍栈在递归算法的内部实现中所起的作用。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第六章：栈与递归
📝1️⃣采用递归算法解决的问题
所谓递归是指，若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。在以下三种情况下，常常使用递归的方法。
✨递归定义的数学函数
编辑
有很多数学函数是递归定义的。
采取“分治法”进行递归求解的问题需要满足以下三个条件。
- 能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，并且这些处理对象更小且变化有规律。
- 可以通过上述转化而使问题简化。
- 必须有一个明确的递归出口，或称递归的边界。
“分治法”求解递归问题算法的一般形式为：
void p(参数表) { if(递归结束条件成立) 可直接求解; //递归终止的条件 else p(较小的参数); //递归步骤 }
可见，上述阶乘函数和Fibonacci数列的递归过程均与此一般形式相对应。
✨具有递归特性的数据结构
编辑
某些数据结构本身具有递归的特性，则它们的操作可递归地描述。
对于递归的数据结构，相应算法采用递归的方法来实现特别方便。链表的创建和链表结点的遍历输出都可以采用递归的方法。下面通过一个简单的递归算法进行举例介绍。
遍历输出链表中各个结点的递归算法
此算法是从前向后遍历输出链表结点的递归算法，调用此递归函数前，参数p指向单链表的首元结点，在递归过程中，p不断指向后继结点，直到p为NULL时递归结束。
显然，这个问题满足上述给出的采用“分治法”进行递归求解的问题需要满足的三个条件。
【算法步骤】：
- 如果p为NULL，递归结束返回。
- 否则输出p->data，p指向后继结点继续递归。
【算法描述】：
void TraverseList(LinkList p) { if(p==NULL) return; //递归终止 else cout<data<next); //p指向后继指点继续递归 }
在递归算法中，如果当递归结束条件成立，只执行return操作时，“分治法”求解递归问题算法的一般形式可以简化为：
void p(参数表) { if(递归结束条件不成立) p(较小的参数); }
因此，上述算法可以简化为：
void TraverseList(LinkList p) { if(p) { cout<data<next); } }
后面章节要介绍的广义表、二叉树等也是典型的具有递归特性的数据结构，其相应算法也可采用递归的方法来实现。
✨问题的解法是递归的
还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单。
例如：汉诺塔问题，迷宫问题等等，这里不再详细介绍。
📝2️⃣递归过程与递归工作栈
一个递归函数，在函数的执行过程中，需多次进行自我调用。
与汇编语言程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需通过栈来进行。
通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：
- 将所有的实参、返回地址等信息传递给被调用函数保存；
- 为被调用函数的局部变量分配存储区；
- 将控制转移到被调函数的入口。
而从被调用函数返回调用函数之前，系统也应完成3件工作：
- 保存被调函数的计算结果；
- 释放被调函数的数据区；
- 依照被调函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则。
编辑
编辑
【图片来源于：https://blog.csdn.net/weixin_40139164/article/details/108964924】
上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。
一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的“层次”。
假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入“下一层”，即第i + 1层。反之，退出第i层递归应返回至“上一层”，即第i − 1层。
为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个工作记录，其中包括所有的实参、所有的局部变量，以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”。
下面阶乘函数Fact(4)为例，介绍递归过程中递归工作栈和活动记录的使用。
主函数调用Fact(4)，当函数运行结束后，控制返回到RetLoc1，在此处n被赋为24（即4!）
void main( ) { long n; //调用Fact (4)时记录进栈 n=Fact(4); //返回地址RetLoc1在赋值语句 RetLoc1 }
为说明方便起见，将阶乘函数算法改写为：
//为说明方便起见，将阶乘函数算法改写为： long Fact(long n ) { long temp; if (n==0) return 1; //活动记录退栈 else temp=n*Fact(n-1); //活动记录进栈 //返回地址RetLoc2在计算语句 RetLoc2 return temp; //活动记录退栈 }
这里暂忽略局部变量temp的入栈和出栈情况。RetLoc2是递归调用Fact (n-1)的返回地址，当Fact(n-1)结束后，返回到RetLoc2，在此处计算n*(n-1)!，然后将结果赋给临时变量temp。
编辑
主函数执行后依次启动了5个函数调用。主程序外部调用Fact(4)的活动记录在栈底，Fact (1)调用Fact (0)进栈的活动记录在栈顶。
递归结束条件出现于函数Fact(0)的内部，执行Fact(0)引起了返回语句的执行。退出栈顶的活动记录，返回地址返回到上一层Fact(1)的调用递归处RetLoc2，继续执行语句temp=1*1，接着执行return temp又引起新的退栈操作。此退栈过程直至Fact(4)执行完毕后，将控制权转移给main为止。
📝3️⃣递归算法的效率分析
✨时间复杂度分析
在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析可以转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问题，而递归方程的形式多种多样，其求解方法也不一而足。迭代法是求解递归方程的一种常用方法，其基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端（即方程的解）的估计。
下面以阶乘的递归函数Fact(n)为例，说明通过迭代法求解递归方程来计算时间复杂度的方法。
设Fact(n)的执行时间是T(n)。此递归函数中语句if(n==0) return 1;的执行时间是O(1)，递归调用Fact(n-1)的执行时间是T(n-1)，所以else return n*Fact(n-1);的执行时间是O(1)+ T(n-1)。
其中，设两数相乘和赋值操作的执行时间为O(1)，则对某常数C、D有如下递归 方程：
设n>2，利用上式对T(n-1)展开，即在上式中用n-1代替n得到
T(n-1)=C+T(n-2)
再代入T(n)=C+T(n-1)中，有
T(n)=2C+T(n-2)
同理，当n>3时有
T(n)=3C+T(n-3)
依次类推，当n>i时有
T(n) =iC+T(n-i)
最后，当i=n时有
T(n)=nC+T(0)=nC+D
求得递归方程的解为：T(n)=O(n)
采用这种方法计算Fibonacci数列和Hanoi塔问题递归算法的时间复杂度均为O(2n)。
✨空间复杂度分析
递归函数在执行时，系统需设立一个“递归工作栈”存储每一层递归所需的信息，此工作栈是递归函数执行的辅助空间，因此，分析递归算法的空间复杂度需要分析工作栈的大小。
对于递归算法，空间复杂度
S(n) = O(f (n))
其中，f(n)为“递归工作栈”中工作记录的个数与问题规模n的函数关系。
根据这种分析方法不难得到，前面讨论的阶乘问题、Fibonacci数列问题、Hanoi塔问题的递归算法的空间复杂度均为O(n)。
📝4️⃣利用栈将递归转换为非递归的方法
通过上述讨论，可以看出递归程序在执行时需要系统提供隐式栈这种数据结构来实现，对于一般的递归过程，仿照递归算法执行过程中递归工作栈的状态变化可直接写出相应的非递归算法。这种利用栈消除递归过程的步骤如下。
- 设置一个工作栈存放递归工作记录（包括实参、返回地址及局部变量等)。
- 进入非递归调用入口（即被调用程序开始处）将调用程序传来的实在参数和返回地址入栈（递归程序不可以作为主程序，因而可认为初始是被某个调用程序调用)。
- 进入递归调用入口：当不满足递归结束条件时，逐层递归，将实参、返回地址及局部变量入栈，这一过程可用循环语句来实现—模拟递归分解的过程。
- 递归结束条件满足，将到达递归出口的给定常数作为当前的函数值。
- 返回处理：在栈不空的情况下，反复退出栈顶记录，根据记录中的返回地址进行题意规定的操作，即逐层计算当前函数值，直至栈空为止—模拟递归求值过程。
通过以上步骤，可将任何递归算法改写成非递归算法。但改写后的非递归算法和原来比较起来，结构不够清晰，可读性差，有的还需要经过一系列的优化，这里不再举例详述。
由于递归函数结构清晰，程序易读，而且其正确性容易得到证明，因此，利用允许递归调用的语言（如C语言）进行程序设计时，给用户编制程序和调试程序带来很大方便。因为对这样一类递归问题编程时，不需用户自己而由系统来管理递归工作栈。
