递归与迭代

递归和迭代是算法里最基础、也最容易反复遇到的两种思想。

很多题表面上看是在考树、链表、DFS、回溯，实际上最底层还是在考：

  • 这个问题能不能拆成更小的同类子问题
  • 我是应该让函数自己调用自己，还是自己手动维护过程

所以学习递归和迭代，不只是学两种写法，更重要的是理解问题该怎么拆、过程该怎么推进。

1. 什么是递归

递归（Recursion）就是：

一个函数在函数内部直接或间接调用自己。

它的核心思想是：

把原问题拆成一个或多个规模更小、但结构相同的子问题。

例如：

  • 计算阶乘
  • 二叉树遍历
  • 深度优先搜索 DFS
  • 回溯
  • 归并排序

这些问题都很适合递归，因为它们本身就具有明显的“重复子结构”。

1.1 递归最重要的三要素

写递归时一定要先想清楚这三件事：

1. 终止条件

什么时候不再继续调用自己。

2. 递归关系

当前问题和更小子问题之间的关系是什么。

3. 当前层要做什么

当前这一层函数除了“调用下一层”之外，还需要做什么处理。

这三点如果有一点没想清楚，递归通常就会写崩。

1.2 一个最简单的递归例子：阶乘

public int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

这里：

  • 终止条件：n == 1
  • 递归关系：factorial(n) = n * factorial(n - 1)
  • 当前层操作：把当前的 n 乘到子问题结果上

2. 什么是迭代

迭代（Iteration）就是：

通过循环，让状态一步一步向前推进，直到满足结束条件。

最常见的就是：

  • for
  • while

例如还是阶乘：

public int factorial(int n) {
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
    }
    return ans;
}

迭代的核心思想不是“自己调用自己”，而是：

手动维护变量，让问题逐步逼近答案。

3. 递归和迭代的关系

很多初学者会把递归和迭代看成完全不同的东西，但实际上它们经常是在解决同一个问题，只是表达方式不同。

可以这样理解：

  • 递归：把过程交给函数调用栈
  • 迭代：把过程交给自己维护的变量、栈、队列或指针

所以很多递归写法，最后都可以改写成迭代。

最典型的就是：

  • 递归版 DFS
  • 显式栈模拟的迭代版 DFS

4. 什么时候更适合递归

如果一个问题天然满足“分解成同类子问题”的结构，递归往往会更自然。

常见场景：

4.1 树相关问题

树的左右子树本身还是树，所以递归通常最直观。

例如二叉树前序遍历：

public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}

4.2 深度优先搜索 DFS

图、网格、迷宫、连通块问题，递归 DFS 很常见。

4.3 回溯问题

例如：

  • 全排列
  • 子集
  • 组合
  • N 皇后

这类问题本身就带有“做选择 -> 递归 -> 撤销选择”的结构。

4.4 分治问题

例如：

  • 归并排序
  • 快速排序
  • 二分递归写法

这类问题可以天然拆成左右两部分递归解决。

5. 什么时候更适合迭代

有些问题虽然递归能写，但迭代更稳、更省空间、更容易控制细节。

常见场景：

5.1 线性扫描

例如数组、字符串、双指针、滑动窗口问题，通常迭代更合适。

5.2 状态转移清晰的问题

如果状态只需要依赖前一步或前几步，循环写法往往更直接。

例如：

  • 斐波那契数列
  • 动态规划中的线性转移
  • 前缀和

5.3 递归层数可能很深

递归会占用系统调用栈，如果层数太深，可能栈溢出。

这时更适合：

  • 改成迭代
  • 或者显式使用栈模拟递归

6. 递归的优缺点

6.1 优点

  • 思想自然，和“问题拆解”高度一致
  • 树、图、回溯问题写起来更清晰
  • 代码通常更短

6.2 缺点

  • 容易栈溢出
  • 调试时不容易看清每一层状态
  • 有些题递归写出来性能不一定好

尤其要记住：

递归的隐式成本是函数调用栈。

7. 迭代的优缺点

7.1 优点

  • 空间更可控
  • 不容易因为递归太深而爆栈
  • 线性过程通常更直观

7.2 缺点

  • 有些问题写起来不如递归自然
  • 需要自己维护状态，代码可能更繁琐
  • 对复杂树/图问题，迭代写法可读性可能更差

8. 递归的本质：函数栈

理解递归最重要的一点，不是“函数会调用自己”，而是：

每一次递归调用，都会把当前函数的局部变量、参数、返回位置压入调用栈。

可以把它想成一层一层“压栈”：

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

然后在最深处返回，再一层层“出栈”：

factorial(1) = 1
factorial(2) = 2 * 1
factorial(3) = 3 * 2
factorial(4) = 4 * 6

这也是为什么很多递归都可以用“手动栈”改写成迭代。

9. 递归转迭代的核心思路

如果递归本质上依赖的是调用栈，那么想改成迭代时，通常就要自己维护一个数据结构来模拟它。

常见替代方式：

  • 用 Stack / Deque 模拟 DFS
  • 用 Queue 模拟 BFS
  • 用循环变量维护状态推进

例如二叉树前序遍历的迭代写法：

public void preorder(TreeNode root) {
    if (root == null) return;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.val);

        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

这里本质上就是把原来系统帮我们做的“入栈/出栈过程”自己写出来了。

10. 写递归时的常见错误

10.1 忘记终止条件

这是最经典的问题，会直接导致死递归。

10.2 终止条件写错

不是没有终止，而是停得太早或太晚，导致结果错误。

10.3 没想清“当前层要做什么”

很多人只会写“递归调用”，但不知道这一层在递归前后要处理什么。

尤其是树遍历、回溯这类题，当前层的处理非常关键。

10.4 全局变量状态污染

递归时如果用了全局变量、路径数组、visited 数组，一定要想清楚什么时候改、什么时候恢复。

10.5 重复计算

例如朴素递归版斐波那契：

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

它的问题是大量重复计算，时间复杂度很差。

这类情况通常要考虑：

  • 记忆化搜索
  • 动态规划
  • 改成迭代

11. 写迭代时的常见错误

11.1 循环边界写错

例如：

  • 少遍历一个
  • 多遍历一个
  • left <= right 和 left < right 混淆

11.2 状态更新顺序错误

很多迭代问题不是不会写，而是更新顺序一错就全错。

尤其是：

  • 双指针
  • 滑动窗口
  • 动态规划滚动变量

11.3 漏掉初始化

迭代通常要先定义状态变量，初值错了，后面都会错。

12. 如何判断一道题该用递归还是迭代

做题时可以先问自己下面几个问题：

12.1 这个问题能不能拆成规模更小的同类问题

如果能，而且结构很明显，优先想递归。

12.2 这个过程是不是天然是一层一层向下搜索

如果是树、图、回溯、DFS，往往递归更顺手。

12.3 这个过程是不是更像线性推进

如果是数组扫描、双指针、滑动窗口、前缀和，通常优先考虑迭代。

12.4 递归深度会不会很大

如果会很深，就要警惕爆栈，必要时改成迭代。

13. 刷题时的实战记忆法

可以把两者记成下面这组对照：

递归

  • 关键词：拆问题、函数自己调自己、调用栈
  • 常见题型：树、DFS、回溯、分治
  • 核心检查点：终止条件、递归关系、当前层操作

迭代

  • 关键词：循环推进、状态维护、手动控制过程
  • 常见题型：数组、双指针、滑动窗口、线性 DP
  • 核心检查点：初始化、循环边界、更新顺序

14. 一个经典问题：递归一定比迭代慢吗

不一定。

但通常来说：

  • 递归会有函数调用开销
  • 递归会使用额外栈空间
  • 如果有重复计算，递归可能明显更慢

所以很多时候不是“递归不能用”，而是：

递归更适合表达思路，迭代更适合优化和工程控制。

15. 总结

递归和迭代并不是对立关系，而是解决问题的两种表达方式。

递归强调的是：

把大问题拆成小问题，把过程交给调用栈。

迭代强调的是：

用循环和变量一步一步推进，把过程控制权拿在自己手里。

如果以后做题时一时想不清，就优先记住下面这句话：

树、DFS、回溯、分治优先想递归；数组扫描、双指针、滑动窗口、线性状态推进优先想迭代。

再补一句最实用的：

递归写的是问题结构，迭代写的是执行过程。