栈与递归的关系

必备算法：递归！⽆论你是前端开发，还是后端开发，都需要掌握它！递归是⼀种⾮常重要的算法思想，⽆论你是前端开发，还是后端开发，都需要掌握它。

在⽇常⼯作中，统计⽂件夹⼤⼩，解析xml⽂件等等，都需要⽤到递归算法。

它太基础太重要了，这也是为什么⾯试的时候，⾯试官经常让我们⼿写递归算法。

本⽂呢，将跟⼤家⼀起深⼊挖掘⼀下递归算法~什么是递归？递归，在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。

简单来说，递归表现为函数调⽤函数本⾝。

在知乎看到⼀个⽐喻递归的例⼦，个⼈觉得⾮常形象，⼤家看⼀下：❝递归最恰当的⽐喻，就是查词典。

我们使⽤的词典，本⾝就是递归，为了解释⼀个词，需要使⽤更多的词。

当你查⼀个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第⼆个词，可惜，第⼆个词⾥仍然有不懂的词，于是查第三个词，这样查下去，直到有⼀个词的解释是你完全能看懂的，那么递归⾛到了尽头，然后你开始后退，逐个明⽩之前查过的每⼀个词，最终，你明⽩了最开始那个词的意思。

❞来试试⽔，看⼀个递归的代码例⼦吧，如下：递归的特点实际上，递归有两个显著的特征,终⽌条件和⾃⾝调⽤:✿⾃⾝调⽤：原问题可以分解为⼦问题，⼦问题和原问题的求解⽅法是⼀致的，即都是调⽤⾃⾝的同⼀个函数。

✿终⽌条件：递归必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。

结合以上demo代码例⼦，看下递归的特点：递归与栈的关系其实，递归的过程，可以理解为出⼊栈的过程的，这个⽐喻呢，只是为了⽅便读者朋友更好理解递归哈。

以上代码例⼦计算sum（n=3）的出⼊栈图如下：为了更容易理解⼀些，我们来看⼀下函数sum（n=5）的递归执⾏过程，如下：✿计算sum（5）时，先sum（5）⼊栈，然后原问题sum（5）拆分为⼦问题sum（4），再⼊栈，直到终⽌条件sum（n=1）=1，就开始出栈。

✿ sum（1）出栈后，sum（2）开始出栈，接着sum（3）。

✿最后呢，sum（1）就是后进先出，sum（5）是先进后出，因此递归过程可以理解为栈出⼊过程啦~递归的经典应⽤场景哪些问题我们可以考虑使⽤递归来解决呢？即递归的应⽤场景⼀般有哪些呢？✿阶乘问题✿⼆叉树深度✿汉诺塔问题✿斐波那契数列✿快速排序、归并排序（分治算法体现递归）✿遍历⽂件，解析xml⽂件递归解题思路解决递归问题⼀般就三步曲，分别是：✿第⼀步，定义函数功能✿第⼆步，寻找递归终⽌条件✿第⼆步，递推函数的等价关系式这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例⼦来喵喵吧~1、定义函数功能定义函数功能，就是说，你这个函数是⼲嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？⽐如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：2、寻找递归终⽌条件递归的⼀个典型特征就是必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。

栈在递归中的作用栈是一种具有特殊性质的线性数据结构，在其中元素的插入和删除操作只能在栈的顶部进行。

栈的特点是元素按照后进先出的顺序进行处理，即最后插入到栈中的元素最先被访问到。

递归是一种程序设计技巧，通过一个函数在其定义中调用自身来解决问题。

递归函数在解决问题时以一种分而治之的办法，将原始问题划分为较小的子问题，并通过解决子问题来解决原始问题。

那么，栈在递归中起到了什么作用呢？一、存储临时变量：递归函数在每一次调用自身时都会入栈，该栈用来保存每个递归调用时的临时变量。

在递归函数内部定义的变量会保存在栈中，每次函数调用时，这些局部变量都会被压入栈中。

当函数的递归调用完成后，栈中保存的该函数的局部变量会被弹出，以便为下一个递归调用或其他操作提供内存空间。

这样，栈起到了一个保存临时变量的作用。

二、存储函数调用的返回地址：在递归调用时，每次调用后都需要返回到上一层调用处。

栈的另一个作用是存储函数调用的返回地址。

当一个函数调用了自身，并进行了递归调用时，当前函数的上下文信息（包括函数指针、参数和局部变量等）都会被保存在栈中，然后在递归调用完成后，栈中保存的上下文信息将被弹出，返回到上一层函数的下一条执行指令的位置，继续执行下去。

三、维护递归层次关系：递归调用时，每次调用自身都需要将当前的状态保存在栈中，这样可以保留每一次递归调用的上下文信息。

栈的深度也反映了递归的层次关系。

当递归调用层数很大时，栈的深度也会相应增加。

四、确保函数调用的正确性：栈在递归中还发挥了确保函数调用的正确性的作用。

每一次递归调用都会将当前的状态保存在栈中，包括参数、局部变量、返回地址等信息。

这样，即使在递归调用过程中发生了其他函数的调用，当递归调用完成后，栈中保存的状态信息都能够正确恢复，确保程序的正确执行。

总结来说，栈在递归中起到了存储临时变量、存储函数调用的返回地址、维护递归层次关系以及确保函数调用的正确性等作用。

栈的使用使递归函数能够按照正确的顺序进行递归调用，并在递归调用完成后正确返回上一层函数的下一条执行指令的位置。

数据结构之递归Ⅲ递归的三⼤要素// 算 n 的阶乘(假设n不为0)int f(int n){if(n <= 2){return n;}}第三要素：找出函数的等价关系式第三要素就是，我们要不断缩⼩参数的范围，缩⼩之后，我们可以通过⼀些辅助的变量或者操作，使原函数的结果不变。

例如，f(n) 这个范围⽐较⼤，我们可以让 f(n) = n * f(n-1)。

这样，范围就由 n 变成了 n-1 了，范围变⼩了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。

说⽩了，就是要找到原函数的⼀个等价关系式，f(n) 的等价关系式为 n * f(n-1)，即f(n) = n * f(n-1)。

这个等价关系式的寻找，可以说是最难的⼀步了，如果你不⼤懂也没关系，因为你不是天才，你还需要多接触⼏道题，我会在接下来的⽂章中，找 10 道递归题，让你慢慢熟悉起来。

找出了这个等价，继续完善我们的代码，我们把这个等价式写进函数⾥。

如下：// 算 n 的阶乘(假设n不为0)int f(int n){if(n <= 2){return n;}// 把 f(n) 的等价操作写进去return f(n-1) * n;}⾄此，递归三要素已经都写进代码⾥了，所以这个 f(n) 功能的内部代码我们已经写好了。

这就是递归最重要的三要素，每次做递归的时候，你就强迫⾃⼰试着去寻找这三个要素。

还是不懂？没关系，我再按照这个模式讲⼀些题。

有些有点⼩基础的可能觉得我写的太简单了，没耐⼼看？少侠，请继续看，我下⾯还会讲如何优化递归。

当然，⼤佬请随意，可以直接拉动最下⾯留⾔给我⼀些建议，万分感谢！Ⅲ案例1：斐波那契数列斐波那契数列的是这样⼀个数列：1、1、2、3、5、8、13、21、34....，即第⼀项 f(1) = 1,第⼆项 f(2) = 1.....,第 n 项⽬为 f(n) = f(n-1) + f(n-2)。

求第 n 项的值是多少。

后缀表达形式后缀表达式（Reverse Polish Notation，简称RPN）是一种数学表达式的书写方式，与传统的中缀表达式相比具有简洁、易于计算的特点。

本文将介绍后缀表达式的定义、转换方法以及其在计算机科学和数学领域的应用。

一、后缀表达式的定义和特点后缀表达式是一种运算符位于操作数之后的数学表达式。

它的主要特点是省略了括号，并且操作符的优先级通过操作符本身的位置来确定。

例如，中缀表达式“3+4*5”可以转换为后缀表达式“345*+”。

后缀表达式的优势在于它避免了使用括号来标识运算符的优先级，使得表达式的计算更加简洁明了。

同时，后缀表达式的计算过程也更加直观，只需要从左到右依次处理每个操作数和操作符即可。

二、中缀表达式转换为后缀表达式的方法将中缀表达式转换为后缀表达式的方法主要有两种：栈的应用和递归的应用。

1. 栈的应用：通过使用一个运算符栈来实现转换。

遍历中缀表达式中的每个元素，按照以下规则进行处理：- 如果是操作数，则输出到后缀表达式中；- 如果是左括号，则将其压入运算符栈中；- 如果是右括号，则将运算符栈中的运算符依次弹出并输出，直到遇到左括号；- 如果是运算符，则将其与运算符栈栈顶的运算符进行比较：- 如果运算符栈为空或栈顶为左括号，则将当前运算符压入运算符栈中；- 如果当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入运算符栈中；- 否则，将运算符栈栈顶的运算符弹出并输出，然后继续比较当前运算符与新的栈顶运算符的优先级。

2. 递归的应用：通过递归地处理中缀表达式的每个元素来实现转换。

遍历中缀表达式中的每个元素，按照以下规则进行处理：- 如果是操作数，则输出到后缀表达式中；- 如果是运算符，则判断当前运算符与前一个运算符的优先级关系：- 如果当前运算符的优先级大于前一个运算符的优先级，则将当前运算符输出到后缀表达式中；- 否则，将前一个运算符输出到后缀表达式中，然后继续递归处理当前运算符。

栈及其应用第一节栈的基本知识一、栈的基本概念栈（stack，又称为堆栈）是一种特殊的线性表。

作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。

在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。

而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。

如果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。

然而，摞起来的碗实际上仍然是一个线性表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。

一般而言，栈是一个线性表，其所有的插入和删除操作均是限定在线性表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。

若给定一个栈S=（a1, a2，a3，……，a n），则称a1为栈底元素，a n为栈顶元素，元素a i位于元素a i-1之上。

栈中元素按a1, a2，a3，……，a n的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为a n, a n-1，……，a1。

也就是说，栈中元素的进出是按“后进先出”的原则进行，这是栈的重要特征。

因此栈又称为后进先出表(LIFO表—Last In First Out)。

我们常用下图来形象地表示栈：二、栈的存储结构（1）顺序栈栈是一种线性表，在计算机中用一维数组作为栈的存储结构最为简单，操作也最为方便，也是最为常用的。

例如，设一维数组STACK[1..n] 表示一个栈，其中n为栈的容量，即可存放元素的最大个数。

栈的第一个元素，或称栈底元素，是存放在STACK[1]处，第二个元素存放在STACK[2]处，第i个元素存放在STACK[i]处。

另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0；当top=n时，表示栈满。

如果一个栈已经为空，但用户还继续做出栈（读栈）操作，则会出现栈的“下溢”；如果一个栈已经满了，用户还继续做进栈操作，则会出现栈的“上溢”。

一、实验目的1. 理解栈的基本概念、特点及逻辑结构；2. 掌握栈的顺序存储和链式存储结构；3. 熟练掌握栈的基本操作，如入栈、出栈、判断栈空等；4. 理解栈在递归算法中的应用；5. 探究栈在实际问题中的应用。

二、实验内容1. 栈的定义与特点2. 栈的顺序存储结构3. 栈的链式存储结构4. 栈的基本操作5. 栈在递归算法中的应用6. 栈在实际问题中的应用三、实验步骤1. 栈的定义与特点（1）栈是一种后进先出（LIFO）的数据结构；（2）栈的元素只能从一端（栈顶）进行插入和删除操作；（3）栈具有两个基本操作：入栈和出栈。

2. 栈的顺序存储结构（1）使用数组来实现栈的顺序存储结构；（2）定义一个数组作为栈的存储空间；（3）定义栈顶指针top，初始值为-1；（4）定义栈的最大容量maxSize。

3. 栈的链式存储结构（1）使用链表来实现栈的链式存储结构；（2）定义一个链表节点，包含数据域和指针域；（3）定义栈顶指针top，初始时指向链表头节点。

4. 栈的基本操作（1）入栈操作：将元素插入到栈顶，栈顶指针向上移动；（2）出栈操作：删除栈顶元素，栈顶指针向下移动；（3）判断栈空：判断栈顶指针是否为-1，是则栈空，否则栈非空。

5. 栈在递归算法中的应用（1）斐波那契数列的递归算法；（2）汉诺塔问题；（3）迷宫问题。

6. 栈在实际问题中的应用（1）括号匹配问题；（2）表达式求值问题；（3）递归函数的调用栈。

四、实验结果与分析1. 栈的定义与特点通过本次实验，我们深入理解了栈的基本概念、特点及逻辑结构，掌握了栈的后进先出特性。

2. 栈的顺序存储结构使用数组实现栈的顺序存储结构，操作简单高效。

在实验过程中，我们实现了栈的基本操作，如入栈、出栈、判断栈空等。

3. 栈的链式存储结构使用链表实现栈的链式存储结构，具有灵活性和扩展性。

在实验过程中，我们实现了栈的基本操作，如入栈、出栈、判断栈空等。

4. 栈的基本操作通过实验，我们熟练掌握了栈的基本操作，如入栈、出栈、判断栈空等，为后续递归算法和实际问题中的应用奠定了基础。