Lecture 11：栈在递归中的应用

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

11.1 基本概念

定义：#递归

描述：递归是指一个函数在求解问题时，直接或间接调用自身，把原始问题转化为属性相同但规模更小的子问题。

适用场景

原始问题可以分解为规模较小的同类问题。
子问题与原问题具有相同性质。
问题存在明确的递归出口，也就是边界条件。

递归必须包含

递归表达式：把大问题转化为小问题。
边界条件：让递归在某个位置停止。

11.2 递归示例

11.2.1 阶乘

定义：#阶乘递归

描述：计算正整数阶乘时，$n!$ 可以转化为 $n\times(n-1)!$，直到遇到边界条件。

阶乘的递归定义： $$ factorial(n)= \begin{cases} n\times factorial(n-1), & n>1 \ 1, & n=1 \ 1, & n=0 \end{cases} $$

解释

递归表达式： $$ factorial(n)=n\times factorial(n-1) $$
边界条件： $$ factorial(1)=1 $$

$$ factorial(0)=1 $$

11.2.2 斐波那契数列

定义：#斐波那契递归

描述：斐波那契数列中，当前项可以由前两项相加得到。

斐波那契数列的递归定义： $$ Fib(n)= \begin{cases} Fib(n-1)+Fib(n-2), & n>1 \ 1, & n=1 \ 0, & n=0 \end{cases} $$

解释

递归表达式： $$ Fib(n)=Fib(n-1)+Fib(n-2) $$
边界条件： $$ Fib(1)=1 $$

$$ Fib(0)=0 $$

原图的阶乘、斐波那契递归式及边界条件均已完整改写为上方 LaTeX 公式，没有额外的空间结构信息，故不重复嵌图。

11.3 栈和递归的关系

11.3.1 函数调用栈

定义：#递归工作栈

描述：递归调用时，系统会用函数调用栈保存每一层函数调用的信息，这个函数调用栈也称为递归工作栈。

递归调用时需要保存的信息

当前函数的参数。
当前函数的局部变量。
函数返回地址。
当前调用层还没有执行完的上下文。

栈的作用

每调用一次递归函数，就会把当前调用的信息压入栈。
每结束一层递归调用，就会从栈中弹出该层调用的信息。
最后被调用的函数最先执行结束，符合栈的后进先出特点： $$ \text{LIFO}=\text{Last In First Out} $$

11.3.2 为什么递归天然依赖栈

以递归调用为例：

Fib(4)
-> Fib(3)
-> Fib(2)
-> Fib(1)

调用时不断压栈：

Fib(4), Fib(3), Fib(2), Fib(1)

返回时从最后调用的函数开始：

Fib(1) -> Fib(2) -> Fib(3) -> Fib(4)

这正好是： $$ \text{后调用，先返回} $$

11.4 递归实现

11.4.1 斐波那契数列代码

以下教学示例约定输入为非负整数 $n$；负数不满足递归出口条件，不能直接传入。

代码

int Fib(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

对应关系

代码	含义
`if (n == 0) return 0;`	边界条件
`else if (n == 1) return 1;`	边界条件
`return Fib(n - 1) + Fib(n - 2);`	递归表达式

PDF 代码修正

原 PDF 的代码中 int Fib(it n) 应理解为：

int Fib(int n)

11.4.2 递归代码的书写要点

先写边界条件。
再写递归表达式。
每次递归调用必须让问题规模变小。
必须保证递归能够到达边界条件。

错误写法示例

int f(int n) {
    return f(n);
}

问题

问题规模没有变小。
没有边界条件。
会无限递归，最终可能栈溢出。

11.5 递归的缺点

11.5.1 栈溢出

定义：#栈溢出

描述：栈溢出是指函数调用层数过多，递归工作栈无法继续容纳新的调用信息。

原因

递归层数太深。
缺少边界条件。
边界条件写错，递归无法停止。
每层递归保存的信息太多。

后果

程序异常终止。
空间复杂度升高。
实际运行效率降低。

11.5.2 空间复杂度

递归算法除了数据本身，还需要额外的递归工作栈空间。
若递归深度为 $n$，每层调用占用常数空间，则空间复杂度通常为： $$ O(n) $$

阶乘递归

递归深度约为 $n$。
空间复杂度： $$ O(n) $$

普通斐波那契递归

单条调用链最大深度约为 $n$。
空间复杂度： $$ O(n) $$
但它会重复计算大量子问题，时间复杂度较高。

11.6 题型整理

题型：#递归与栈

第一部分：解题方法

看到递归，要想到函数调用栈。
每一次递归调用都会压栈。
每一次函数返回都会出栈。
最后被调用的函数最先结束，体现 LIFO。
递归层数越深，递归工作栈占用空间越多。

第二部分：典型例题

例题 1：递归为什么会用到栈？

答：

因为递归调用需要保存每一层函数的参数、局部变量和返回位置。
函数调用遵循后调用先返回。
这与栈的后进先出性质一致。
所以系统用函数调用栈管理递归过程。

例题 2：递归可能带来什么问题？

答：

递归层数过多时，可能导致栈溢出。
递归工作栈会增加额外空间开销。
若存在重复子问题，还可能导致时间开销很大。

第三部分：知识点复盘

递归不是新的数据结构，但递归执行过程依赖栈。
递归必须有边界条件。
递归必须让问题规模不断缩小。
函数调用栈也可以称为递归工作栈。

11.7 本节复盘

必须掌握

递归适合解决可以分解成同类小规模子问题的问题。
递归包含递归表达式和边界条件。
递归调用使用函数调用栈。
函数调用栈也称递归工作栈。
最后被调用的函数最先执行结束，符合 LIFO。
递归过深可能导致栈溢出。

易错点

递归不等于循环。
没有边界条件的递归会无限调用。
边界条件写错也可能导致栈溢出。
递归算法的空间复杂度要考虑递归工作栈。
斐波那契普通递归容易产生大量重复计算。

一句话总结

递归把大问题变成同类小问题，系统用递归工作栈保存每层调用，所以递归过程本质上体现了栈的后进先出。