Recursion
学习 recursion — 当函数 calls 它自己 — 包含基础情况, call stack, and 当到 use 它.
你将学到
- 什么 recursion 是 and 如何函数 calls 它自己
- 关键 importance 的基础情况
- 如何 call stack tracks recursive calls
- Converting 之间 recursion and iteration
- 当 recursion 是 elegant and 当它 是 wasteful
概念讲解
Recursion
Recursion 是一种 technique where a function calls itself to solve a smaller version of the same problem. It is an alternative to loops (iteration) for repeating work. Some problems — traversing trees, exploring file systems, parsing nested structures — have a naturally recursive shape that makes recursion the clearest solution.
The Two Essential Parts
Every recursive function needs two things:
- Base case — a condition where the function returns without calling itself. This stops the recursion. Without it, the function calls itself forever.
- Recursive case — the function calls itself with a smaller or simpler input, moving toward the base case.
function factorial(n) {
if (n <= 1) return 1; // base case: stop here
return n * factorial(n - 1); // recursive case: call with n-1
}
Each call to factorial reduces n by 1, moving closer to the base case. The calls stack up, then unwind: factorial(4) becomes 4 * factorial(3), which becomes 4 * 3 * factorial(2), and so on until factorial(1) returns 1.
The Call Stack
When a function calls itself, each call is placed on the call stack — a data structure that tracks which function is currently running and what to return to. The stack grows with each recursive call and shrinks as each call returns. If the recursion is too deep, the stack overflows, producing a stack overflow error. This is why every recursive function must reach its base case in a finite number of steps.
Recursion vs. Iteration
Any recursive function can be rewritten as a loop, and vice versa. The choice depends on clarity:
- Iteration is usually faster and uses less memory (no call stack growth).
- Recursion is clearer for problems with a naturally recursive structure: tree traversal, divide-and-conquer algorithms, nested data processing.
For example, calculating a factorial is equally clear either way. But traversing a file directory — where each folder can contain more folders — is far more elegant with recursion.
When to Use Recursion
Use recursion when the problem is naturally self-similar: "做某事, 然后做相同 thing on smaller 片段." Avoid recursion when a simple loop would do the same job more efficiently. In JavaScript, deep recursion (thousands of calls) can cause stack overflow, so for very deep structures, an iterative approach with an explicit stack may be necessary.
Recursion is a thinking tool as much as a coding technique. Learning it trains you to break problems into smaller subproblems — a skill that applies even when you end up writing iterative code.
示例代码
// Recursive: calculate factorial
function factorial(n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)
// Recursive: flatten a nested array
function flatten(arr) {
const result = [];
for (const item of arr) {
if (Array.isArray(item)) {
// Recursive case: item is an array, flatten it
result.push(...flatten(item));
} else {
// Base case: item is not an array, add directly
result.push(item);
}
}
return result;
}
console.log(flatten([1, [2, [3, [4]]], 5])); // [1, 2, 3, 4, 5]
// Recursive: countdown with a clear base case
function countdown(n) {
if (n < 0) return; // base case: stop
console.log(n);
countdown(n - 1); // recursive case
}
countdown(3); // prints 3, 2, 1, 0
factorial shows classic recursive 模式. flatten demonstrates recursion on nested 数据 — 每个 nested 数组触发 another recursive call. countdown 是 simplest 示例使用清晰基础情况.
动手试一试
- JSON 树 Viewer
Nested JSON 是 rendered using recursion — 每个 nested 对象 or 数组触发 another level 的渲染函数.
- JSON Formatter
格式化 nested JSON 需要 recursive descent 通过结构. 粘贴 deeply nested 数据到 see 它 in 操作.
常见错误
错误写法
Forgetting 基础情况, causing 无限 recursion and stack overflow.
正确做法
总是编写基础情况首先. Ask: '什么是 simplest 输入哪里 I know 答案?' 返回那个答案 directly 之前任何 recursive call.
错误写法
制作 recursive call 使用相同输入, 从不 moving 朝向基础情况.
正确做法
每个 recursive call 必须 simplify 输入 — reduce 数字, shorten 列表, shrink 字符串. 如果输入做 不更改, recursion 从不 terminates.
错误写法
Using recursion for 简单 counting 当循环会 是 clearer and faster.
正确做法
如果 for 循环能 express 解答 in 3 行, use 循环. Reserve recursion for naturally recursive problems 如树 traversal or nested 数据.
相关资源
相关速查表
- JavaScript Cheatsheet
引用 for 函数定义, call stack, and ES 模块语法.
练习 Recursion
6 个练习
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。