栈在递归中的应用

递归三要素

• 递归表达式（递推关系）：如何把大问题拆成小问题。例如Fact(n) = n * Fact(n-1)。
• 边界条件（递归出口）：何时不再调用自身。例如if(n==1) return 1;。
• 向终止条件递推：每次递归调用都向终止条件靠近（如n逐渐减小到1）。

递归本质：函数自己调用自己，每一次递归调用都会生成新栈帧压入系统栈；函数执行完毕，栈帧出栈。
完美契合栈LIFO 后进先出：最后调用的函数最先执行完毕返回。
适合用递归算法解决：可以把原始问题转换为属性相同，但规模较小的问题。

底层机制（栈的应用）

函数调用的特点：最后被调用的函数最先执行结束（LIFO）
每次函数调用时，需要一个“函数调用栈”，存储：

1. 函数返回地址（调用结束回到上一层代码要执行的位置）
2. 实参
3. 局部变量

区分：
系统栈（运行时自动维护）；我们自己代码写的栈是用户自定义栈。
递归使用系统栈；递归转非递归，需要手动模拟、使用自定义栈。

递归调用时，函数调用栈可称为“递归工作栈”
每进入一层递归，就将递归调用所需信息压入栈顶
每退出一层递归，就从栈顶弹出相应信息（当每一次函数调用结束之后，就弹出栈）

递归的缺点：
效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算。

可以自定义栈将递归算法改造成非递归算法。