递归
最后更新
递归就是函数调用自身，去解决同一个问题的更小版本，直到问题小到可以直接给出答案。这种可以直接回答的情况叫作基线条件（base case），每个递归函数都需要一个：fib(n) 不断拆分成 fib(n - 1) 和 fib(n - 2)，直到遇到 fib(1) 或 fib(0)，它们直接返回自身的值。上方的可视化运行的正是这个过程：点击“播放”，观看调用如何分叉成一棵树，在叶子处到达基线条件，再把值逐层向上返回，在每一层合并结果。
动画展示的第二样东西是调用栈：所有已经开始但还没返回的调用。调用越深，栈越高，在递归深度处达到最高点，随着结果返回又逐渐展开。这就是为什么深层递归可能导致栈溢出，而迭代循环从不增加栈的高度。同样的调用结构也驱动着深度优先搜索、归并排序，以及二叉树上的大多数操作。
时间复杂度与空间复杂度
以上方演示的朴素递归斐波那契为例，并对比两种标准的改进方法：
| 方法 | 时间 | 空间 | 说明 |
|---|---|---|---|
| 朴素递归 | O(2^n) | O(n) | 调用树每一层都翻倍；空间取决于最深的栈，而不是整棵树。 |
| 使用记忆化 | O(n) | O(n) | 每个 fib(k) 只计算一次并缓存起来；重复的子树变成了查表。 |
| 迭代循环 | O(n) | O(1) | 用两个滚动变量完全取代栈。 |
| 一般的递归 | 调用次数 × 每次调用的工作量 | O(max depth) | 每个已开始但尚未返回的调用都在栈中占一个栈帧。 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 第一个调用 fib(n) 被压入调用栈。 |
| 2 | 它需要 fib(n - 1)，于是这个调用也被压入栈中；父调用等待。 |
| 3 | 调用不断嵌套，直到某次调用遇到 n <= 1：基线条件立即给出答案，不再继续深入。 |
| 4 | 基线条件的值返回给父调用，父调用这时可以开始第二个调用 fib(n - 2)。 |
| 5 | 两个子调用都返回后，父调用把结果相加并返回；它的栈帧离开调用栈。 |
| 6 | 返回过程沿着树一路向上，直到第一个调用的栈帧带着最终答案弹出，栈清空。 |
实例演示
按照动画播放的顺序，精确地计算 fib(4)：
| 调用 | 此刻的调用栈 | 返回值 |
|---|---|---|
fib(4) | fib(4) | 等待子调用 |
fib(3) | fib(4) > fib(3) | 等待子调用 |
fib(2) | fib(4) > fib(3) > fib(2) | 等待子调用 |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1（基线条件） |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0（基线条件） |
fib(2) 合并 | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1（基线条件） |
fib(3) 合并 | fib(4) > fib(3) | 1 + 1 = 2 |
再次 fib(2) | fib(4) > fib(2) | 1，从头重新计算 |
fib(4) 合并 | fib(4) | 2 + 1 = 3 |
什么时候用递归
| 适合使用 | 不适合使用 |
|---|---|
| 问题具有自相似性：树、嵌套结构、分治 | 一个简单的循环就能表达同样的逻辑，而且不需要栈帧 |
递归深度有上限且不大，例如归并排序中的 O(log n) | 输入很大时深度可能达到输入规模，有栈溢出的风险 |
| 回溯需要借助栈记住从哪里继续 | 相同的子问题反复出现，而你没有缓存结果 |
| 递归版本明显更容易阅读和验证 | 你处在热点循环中，函数调用开销会明显影响性能 |
Recursion 代码
简洁、可运行的 Recursion 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Recursion 的 Python 代码
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Recursion 的 JavaScript 代码
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Recursion 的 Java 代码
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Recursion 的 C++ 代码
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Recursion 的 C 代码
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}递归常见问题
递归中的基线条件是什么？
就是小到不需要再递归调用就能直接回答的输入。对
fib(n) 来说是 n <= 1，这时直接返回 n。如果没有可以到达的基线条件，调用就永远不会停止，栈不断增长，程序最终因栈溢出而崩溃。调用栈是什么？为什么它很重要？
运行时会为每个已开始但尚未返回的调用保留一个栈帧，存放它的参数和局部变量。递归深度就等于栈的高度，所以深入
n 层的递归会占用 O(n) 内存，即使每次调用几乎什么都不做。动画下方的那一排标签展示的正是这个栈的增长和展开。为什么递归计算斐波那契数需要指数时间？
因为相同的子问题被一遍又一遍地重复计算：在上面的实例中，
fib(4) 内部计算了两次 fib(2)，而且重复的次数大约每一层翻一倍，总共要 O(2^n) 次调用。在第一次计算时就把每个结果缓存起来，这种方法叫作记忆化，它能把这棵树压缩到 O(n)。递归比迭代更好吗？
两者没有绝对的优劣。每个递归都可以改写成使用显式栈的循环，每个循环也都可以改写成递归。对于树的遍历和深度优先搜索这类自相似的问题，递归的可读性更好；对于线性的遍历，迭代在内存和调用开销上更有优势。
递归函数为什么会栈溢出？
要么是缺少基线条件或基线条件无法到达，导致调用永不停止；要么是递归本身没错，但深度超出了运行时的栈限制，比如在数百万个元素的输入上每个元素递归一次。解决办法是确保能到达基线条件、限制递归深度，或者改写成迭代。
相关资源
更多可视化
