第45章 递归算法

递归(Recursion)指在函数的定义中直接或间接调用函数自身的过程。它通过将复杂大问题拆解为结构相同、规模更小的子问题，先求解小规模基础情况，再反向推导原问题答案。

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 核心三大特征

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

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

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

45.3 标准递归函数结构

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

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

1. factorial(3) → 调用factorial(2)
2. factorial(2) → 调用factorial(1)
3. factorial(1) → 调用factorial(0)
4. factorial(0) 满足出口，返回1
5. 回代：$1\times1=1$ → $2\times1=2$ → $3\times2=6$，最终返回6 每层调用都会在函数调用栈开辟栈帧，存储局部变量与返回地址。

45.5 典型递归示例

45.5.1 斐波那契数列

定义：

$$\begin{cases} fib(0)=0,\ fib(1)=1 \\ fib(n)=fib(n-1)+fib(n-1) \quad n\ge2 \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个盘子，大盘不能压小盘。 递归思路：

1. 将$n-1$个盘子从A借助B移到C；
2. 把最大盘子从A移到C；
3. 将$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 适合使用递归

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

45.9.2 局限性

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

45.10 编码注意事项

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