4.4 递归

什么是递归

递归（Recursion）是指函数在自身内部调用自身的编程技巧。递归是解决某些具有「自相似」结构问题的自然方式——即一个大问题可以被拆分为形式相同但规模更小的子问题。

每个递归函数都必须包含两个要素：

基准情况（Base Case）— 不再递归的终止条件，直接返回结果
递归步骤（Recursive Step）— 将问题缩小，调用自身处理更小的子问题

缺少基准情况会导致无限递归，最终耗尽栈空间（Stack Overflow）。

经典示例：阶乘

n 的阶乘定义为：

n! = n × (n-1) × (n-2) × ... × 2 × 1
0! = 1

这个定义本身就是递归的：n! = n × (n-1)!，基准情况是 0! = 1。

int factorial(int n) {
    if (n <= 1) {        // 基准情况
        return 1;
    }
    return n * factorial(n - 1);   // 递归步骤
}

int main() {
    std::cout << "5! = " << factorial(5) << std::endl;
    // 输出：5! = 120
    return 0;
}

调用 factorial(5) 的展开过程：

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

经典示例：斐波那契数列

斐波那契数列（Fibonacci Sequence）的定义：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)  （n ≥ 2）

直接翻译为递归函数：

int fibonacci(int n) {
    if (n <= 0) return 0;   // 基准情况 1
    if (n == 1) return 1;   // 基准情况 2
    return fibonacci(n - 1) + fibonacci(n - 2);   // 递归步骤
}

这个实现虽然直观，但效率极低。计算 fibonacci(5) 时，fibonacci(3) 会被重复计算多次。随着 n 的增大，重复计算量呈指数级增长。

{% hint style=“warning” %} 上述斐波那契递归实现的时间复杂度为 O(2^n)，仅适用于演示递归概念。实际使用中应改为循环实现或使用记忆化（Memoization）技术来避免重复计算。 {% endhint %}

用循环实现的高效版本：

int fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

递归与栈

每次函数调用，系统都会在调用栈（Call Stack）上分配一块内存（称为栈帧，Stack Frame），用于存储该次调用的参数、局部变量和返回地址。递归调用会不断压入新的栈帧，直到遇到基准情况后才开始逐层返回。

调用栈的空间是有限的。如果递归层级过深（例如 factorial(100000)），栈帧会耗尽可用空间，导致栈溢出（Stack Overflow）。因此，递归适合处理问题规模较小或递归深度可控的场景。

何时使用递归

递归适合以下场景：

问题具有递归结构 — 如树的遍历、图的搜索、分治算法
代码简洁性优先 — 递归实现往往比等价的循环实现更简短、更易理解
递归深度可控 — 不会导致栈溢出

不适合递归的场景：

简单的重复计算 — 用循环更直接
递归深度可能很大 — 有栈溢出风险
存在大量重复子问题 — 朴素递归效率低下，需要额外的优化手段

一般规则：如果递归和循环都能清晰地表达逻辑，优先选择循环；当问题本身是递归定义的（如树结构），递归通常是更自然的选择。