Skip to content

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:

  1. Base case — a condition where the function returns without calling itself. This stops the recursion. Without it, the function calls itself forever.
  2. 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 数据.

相关速查表

练习 Recursion

6 个练习

练习 Recursion

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误