递归入门

递归是函数直接或间接调用自己。链表、树、图上的很多算法，以及分治、回溯，用递归表达往往最自然。

本文解决什么问题

• 递归三要素如何保证「能停、算对」
• 调用栈在干什么
• 递归与循环如何互化
• 常见坑：爆栈、重复计算、缺少终止条件

递归三要素

1. 终止条件（基准情形）：什么时候不再调用自己
2. 问题规模缩小：每次调用都更接近终止
3. 返回结果可组合：用子问题答案拼出当前答案

缺终止条件 → 无限递归直至栈溢出；规模不缩小 → 同样爆栈或算不对。

例子：阶乘

定义：$n! = n \times (n-1)!$，且 $0! = 1$（通常也令 $1! = 1$）。

long long factorial(int n) {
    if (n < 0) {
        /* 视需求报错；这里简单返回 -1 表示非法 */
        return -1;
    }
    if (n <= 1) {
        return 1;                      /* 终止 */
    }
    return n * factorial(n - 1);       /* 规模 n → n-1 */
}

long long factorial(int n) {
    if (n < 0) return -1;
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

时间 $O(n)$，递归深度 $O(n)$，因此额外栈空间也是 $O(n)$。

调用栈在干什么

以 factorial(3) 为例，可以想象栈帧一层层压入，再一层层返回：

factorial(3)
  └─ factorial(2)
       └─ factorial(1)  → 返回 1
     ← 返回 2 * 1 = 2
  ← 返回 3 * 2 = 6

每一层都要保存：返回地址、局部变量、参数等。深度太大时，操作系统给线程的栈不够用，就会栈溢出（stack overflow）。

提示

树的深度优先遍历若写递归，树很歪、深度接近 $n$ 时，可能比「显式栈 + 循环」更容易爆栈。嵌入式或默认栈较小的环境更要小心。

例子：斐波那契（先理解，再谈优化）

定义：$F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)$。

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

这个写法语义正确，但有大量重复计算：fib(n) 的递归树会指数膨胀，时间约 $\Theta(\varphi^n)$ 量级（$\varphi$ 为黄金比），$n = 40$ 左右就明显变慢。

改进方向（后续动态规划章节会系统讲）：

• 改成自底向上循环
• 或加记忆化（memo），同一 $n$ 只算一次

/* 迭代版：O(n) 时间，O(1) 额外空间 */
long long fib_iter(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

递归与迭代可以互化

理论上，递归都能用显式栈改成循环；许多尾递归还能直接改成普通循环。选择标准通常是：

更适合递归	更适合循环 / 显式栈
问题定义本身递归（树、分治）	深度很大，担心爆栈
代码更短、更贴定义	热路径上要抠性能与常数
深度可控（如 $\log n$）	需要精确控制内存

再看一个结构上的递归：链表长度

typedef struct Node {
    int data;
    struct Node *next;
} Node;

int list_len(const Node *head) {
    if (head == NULL) return 0;           /* 空表：终止 */
    return 1 + list_len(head->next);      /* 去掉头结点 */
}

对很长的链表，这种写法深度为 $O(n)$，生产代码里更常见的是 while 计数。这里用来体会「结构递归」：子问题是「去掉头之后的链表」。

常见错误与排查

现象	可能原因	怎么查
程序直接崩溃 / 段错误	无限递归或深度过大	检查终止条件；临时加打印深度；改小输入
结果偶发错误	终止条件写错（如 n==0 漏了负数）	列出最小若干输入的手算对照
极慢	重复子问题（斐波那契式）	画递归树；改记忆化或迭代
局部变量「串台」	误用静态变量 / 全局状态	递归函数尽量用参数传递状态

注意

不要在递归里对同一块内存既修改又依赖未定义的中间状态，除非你非常清楚调用顺序。树删除、释放结点时，常见写法是后序：先递归处理孩子，再释放自己。

和本教程后续内容的联系

• 分治法、归并 / 快速排序：典型递归框架
• 二叉树遍历、DFS：递归或显式栈等价
• 动态规划：常从「会爆的递归」加记忆化或改递推而来

小结

• 递归 = 用同构的小问题描述大问题
• 先保证终止与规模缩小，再谈性能
• 调用栈有深度上限；必要时改迭代或显式栈

下一章进入 基本算法设计思想，从蛮力法开始建立「先正确、再加速」的习惯。