第45章递归算法

递归（Recursion）指在函数的定义中直接或间接调用函数自身的过程。它通过将复杂大问题拆解为结构相同、规模更小的子问题，先求解小规模基础情况，再反向推导原问题答案。本章对应 GESP C++ 五级知识块 6：递归算法，要求掌握递归基本原理、能分析其时间与空间复杂度，并了解递归的优化策略。

factorial(3) 递归调用栈与回代

45.1 递归算法的基本概念

45.1.1 定义示例

阶乘递归定义：

\begin{cases} 0! = 1 \quad &(\text{基础情况}) \\ n! = n \times (n-1)! \quad &(n>0,\text{递归分解}) \end{cases}

对应代码：

int factorial(int n) {
    if (n == 0) {
        return 1; // base case 终止条件
    } else {
        return n * factorial(n - 1);
    }
}

45.1.2 核心三大特征

问题相似性：子问题和原问题逻辑完全一致，仅规模缩小；
规模递减：每次递归参数一定变小，保证能抵达终止条件；
终止条件（Base Case）：存在无需递归直接求解的最小子问题，防止无限递归栈溢出。

45.2 递归三要素（缺一不可）

基本情况（终止条件）：递归出口，无此会无限调用栈溢出。例： $n=0$ 阶乘返回 1；
递归关系式：描述原问题与子问题的计算关系，如 $\text{fib}(n)=\text{fib}(n-1)+\text{fib}(n-2)$ ；
规模递减：每次递归输入严格缩小，逐步靠近出口。

45.3 标准递归函数结构

返回类型 递归函数(参数) {
    if (满足基础条件) {
        return 基础结果; // 终止
    } else {
        // 分解，递归求子问题，合并返回
        return 递归处理缩小后的参数;
    }
}

45.4 递归执行流程（以 factorial(3) 举例）

factorial(3) → 调用 factorial(2)
factorial(2) → 调用 factorial(1)
factorial(1) → 调用 factorial(0)
factorial(0) 满足出口，返回 1
回代： $1 \times 1 = 1$ → $2 \times 1 = 2$ → $3 \times 2 = 6$ ，最终返回 6

每层调用都会在函数调用栈开辟栈帧，存储局部变量与返回地址。

45.5 典型递归示例

45.5.1 斐波那契数列

定义：

\begin{cases} \text{fib}(0)=0,\ \text{fib}(1)=1 \\ \text{fib}(n)=\text{fib}(n-1)+\text{fib}(n-2) \quad n\ge 2 \end{cases}

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

45.5.2 汉诺塔

规则：三根柱子 A（源）、B（辅助）、C（目标），每次只能移动 1 个盘子，大盘不能压小盘。

递归思路：

将 $n-1$ 个盘子从 A 借助 B 移到 C；
把最大盘子从 A 移到 C；
将 $n-1$ 个盘子从 B 借助 A 移到 C。

#include <iostream>
using namespace std;
void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    // 第一步：n-1 个移到辅助柱
    hanoi(n - 1, from, to, aux);
    // 移动最底层大盘
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    // 第二步：n-1 个移到目标柱
    hanoi(n - 1, aux, from, to);
}

45.6 复杂度分析

45.6.1 时间复杂度

由递归总调用次数决定：

阶乘递归： $O(n)$ ，共 $n+1$ 次调用；
朴素斐波那契： $O(2^n)$ ，大量重复计算；
二分查找递归： $O(\log n)$ 。

45.6.2 空间复杂度

等于递归调用栈的最大深度：

阶乘：栈深 $n$ ，空间 $O(n)$ ；
二分查找：栈深 $\log n$ ，空间 $O(\log n)$ 。

45.7 递归 vs 递推（迭代）

对比项	递归	递推（循环）
实现方式	函数自调用	循环迭代
性能	存在函数调用开销，部分场景重复计算	无调用开销，无重复计算
空间开销	依赖递归栈深度	仅常数/一维变量， $O(1)$ 常见
可读性	天然匹配数学递归定义，逻辑简洁	需手动推导迭代公式

斐波那契递推优化：

int fibIterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, res;
    for (int i = 2; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return b;
}

45.8 递归优化方案

45.8.1 记忆化（缓存子问题结果）

解决斐波那契重复计算，用数组存储已求解值：

#include <vector>
using namespace std;
vector<int> memo;
int fibMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}
// 调用入口
int fib(int n) {
    memo.resize(n + 1, 0);
    return fibMemo(n);
}

45.8.2 尾递归

递归调用是函数最后一条执行语句，编译器可优化栈空间至 $O(1)$ ；阶乘尾递归实现：

// 辅助累积函数
int factorialTailHelper(int n, int acc) {
    if (n == 0) return acc;
    return factorialTailHelper(n - 1, n * acc);
}
// 对外接口
int factorialTail(int n) {
    return factorialTailHelper(n, 1);
}

注意：C++ 标准不强制开启尾递归优化，不同编译器支持不同。

45.9 适用场景与局限

45.9.1 适合使用递归

数据天然递归结构：二叉树、DFS 图遍历、分治排序；
数学递归定义：阶乘、斐波那契、组合数；
分支回溯类问题：汉诺塔、迷宫、全排列。

45.9.2 局限性

栈溢出：递归深度过大会触发栈溢出（如 $n=10000$ 阶乘）；
性能损耗：频繁函数调用耗时；
重复子问题（无记忆化时指数复杂度）。

45.10 编码注意事项

必须写清终止条件，杜绝死递归；
大规模数据优先迭代，防止栈溢出；
重叠子问题使用记忆化缓存；
调试可打印递归参数追踪调用栈。

45.11 选择题练习

递归函数必不可少的部分是： A. 两个递归调用 B. 终止条件（基线情况） C. 循环语句 D. 全局变量

查看答案
答案：B。缺少终止条件会无限递归直至栈溢出；递归不一定需要循环或全局变量，一般只需一个递归调用即可。
设 fib(n) 为朴素递归斐波那契，其时间复杂度约为： A. $O(n)$ B. $O(\log n)$ C. $O(2^n)$ D. $O(n^2)$

查看答案
答案：C。朴素递归存在大量重复子问题，调用次数呈指数增长，约 $O(2^n)$ 。
factorial(n) 递归版本的空间复杂度是： A. $O(1)$ B. $O(n)$ C. $O(n^2)$ D. $O(\log n)$

查看答案
答案：B。递归深度为 $n$ ，调用栈最大深度 $n$ ，故空间复杂度 $O(n)$ 。
下列最不适合用递归解决的是： A. 汉诺塔 B. 求 $n!$ C. 对一个 100 万个元素的数组求和（仅用普通递归不优化） D. 树的遍历

查看答案
答案：C。百万级递归深度会直接栈溢出；其余三类天然适合递归。
记忆化优化主要用于解决递归中的： A. 栈溢出 B. 重复子问题导致的重复计算 C. 代码可读性差 D. 输入错误

查看答案
答案：B。记忆化缓存已求解的子问题，避免重复计算（如朴素斐波那契的指数复杂度降为 $O(n)$ ）。