递归函数：用函数调用自身解决问题

什么是递归

站在两面平行的镜子之间, 你会看到无数个自己的倒影——每个倒影中又包含着更小的倒影, 一直延伸到无限远。这就是递归的直观体现:自我指向、自我包含。

在编程中, 递归是一种函数调用自身的技术。一个递归函数会将大问题分解为更小的相同问题, 直到问题小到可以直接解决为止。

递归有两个关键要素:

1. 基础情况(Base Case): 递归的终止条件
2. 递归情况(Recursive Case): 函数调用自身来解决更小的问题

理解递归思维

1. 最简单的递归示例

// 倒计时: 从 n 数到 1
function countdown(n) {
  // 基础情况: 当 n 为 0 时停止
  if (n === 0) {
    console.log("发射!");
    return;
  }

  // 递归情况: 输出当前数字, 然后递归调用更小的数
  console.log(n);
  countdown(n - 1);
}

countdown(5);
// 5
// 4
// 3
// 2
// 1
// 发射!

这个函数是如何工作的? 让我们追踪调用栈:

countdown(5)
  -> 输出 5, 调用 countdown(4)
    -> 输出 4, 调用 countdown(3)
      -> 输出 3, 调用 countdown(2)
        -> 输出 2, 调用 countdown(1)
          -> 输出 1, 调用 countdown(0)
            -> 输出 "发射!", 返回
          <- 返回
        <- 返回
      <- 返回
    <- 返回
  <- 返回

2. 计算阶乘

阶乘是递归的经典示例。5! = 5 × 4 × 3 × 2 × 1 = 120:

// 递归方式
function factorial(n) {
  // 基础情况
  if (n === 0 || n === 1) {
    return 1;
  }

  // 递归情况: n! = n × (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
console.log(factorial(0)); // 1
console.log(factorial(10)); // 3628800

// 对比迭代方式
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

递归版本更接近数学定义, 更易理解, 但会创建多个函数调用。

3. 斐波那契数列

每个数是前两个数之和: 0, 1, 1, 2, 3, 5, 8, 13, 21...

// 基础递归实现
function fibonacci(n) {
  // 基础情况
  if (n <= 1) {
    return n;
  }

  // 递归情况: fib(n) = fib(n-1) + fib(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 8
console.log(fibonacci(10)); // 55

// 调用树可视化 (fibonacci(5))
//                 fib(5)
//              /          \
//         fib(4)          fib(3)
//        /      \        /      \
//    fib(3)   fib(2)  fib(2)  fib(1)
//    /   \    /   \   /   \
// fib(2) fib(1) ...  ...
// 注意: 有大量重复计算!

递归的常见模式

1. 求和数组

// 递归求和
function sum(arr) {
  // 基础情况: 空数组
  if (arr.length === 0) {
    return 0;
  }

  // 递归情况: 第一个元素 + 剩余元素的和
  return arr[0] + sum(arr.slice(1));
}

console.log(sum([1, 2, 3, 4, 5])); // 15

// 更高效的尾递归版本
function sumTail(arr, accumulator = 0) {
  if (arr.length === 0) {
    return accumulator;
  }

  return sumTail(arr.slice(1), accumulator + arr[0]);
}

console.log(sumTail([1, 2, 3, 4, 5])); // 15

2. 查找最大值

function findMax(arr) {
  // 基础情况: 只有一个元素
  if (arr.length === 1) {
    return arr[0];
  }

  // 递归情况: 当前元素 vs 剩余元素的最大值
  const maxOfRest = findMax(arr.slice(1));
  return arr[0] > maxOfRest ? arr[0] : maxOfRest;
}

console.log(findMax([3, 1, 4, 1, 5, 9, 2, 6])); // 9

3. 数组展平

// 递归展平嵌套数组
function flatten(arr) {
  let result = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      // 递归展平子数组
      result = result.concat(flatten(item));
    } else {
      result.push(item);
    }
  }

  return result;
}

const nested = [1, [2, [3, [4]], 5], 6];
console.log(flatten(nested)); // [1, 2, 3, 4, 5, 6]

// 函数式版本
function flattenFunctional(arr) {
  return arr.reduce(
    (acc, item) =>
      Array.isArray(item)
        ? acc.concat(flattenFunctional(item))
        : acc.concat(item),
    []
  );
}

树结构的递归遍历

递归特别适合处理树形结构:

1. DOM 树遍历

// 递归遍历 DOM 树
function traverseDOM(node, callback, level = 0) {
  // 基础情况: 没有节点
  if (!node) return;

  // 处理当前节点
  callback(node, level);

  // 递归处理子节点
  for (const child of node.children) {
    traverseDOM(child, callback, level + 1);
  }
}

// 使用示例
traverseDOM(document.body, (node, level) => {
  const indent = "  ".repeat(level);
  console.log(
    `${indent}${node.tagName} #${node.id || ""} .${node.className || ""}`
  );
});

2. 文件系统遍历

// 递归遍历文件系统结构
function traverseFileSystem(node, callback, path = "") {
  const currentPath = path + "/" + node.name;

  // 处理当前节点
  callback(node, currentPath);

  // 如果是目录, 递归处理子项
  if (node.type === "directory" && node.children) {
    for (const child of node.children) {
      traverseFileSystem(child, callback, currentPath);
    }
  }
}

// 示例数据
const fileSystem = {
  name: "root",
  type: "directory",
  children: [
    {
      name: "documents",
      type: "directory",
      children: [
        { name: "resume.pdf", type: "file" },
        { name: "letter.docx", type: "file" },
      ],
    },
    {
      name: "images",
      type: "directory",
      children: [{ name: "photo1.jpg", type: "file" }],
    },
    { name: "notes.txt", type: "file" },
  ],
};

// 使用
traverseFileSystem(fileSystem, (node, path) => {
  const type = node.type === "directory" ? "📁" : "📄";
  console.log(`${type} ${path}`);
});

3. JSON 深度克隆

function deepClone(obj) {
  // 基础情况: 原始类型
  if (obj === null || typeof obj !== "object") {
    return obj;
  }

  // 处理数组
  if (Array.isArray(obj)) {
    return obj.map((item) => deepClone(item));
  }

  // 处理日期
  if (obj instanceof Date) {
    return new Date(obj);
  }

  // 处理对象
  const cloned = {};
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloned[key] = deepClone(obj[key]);
    }
  }

  return cloned;
}

// 测试
const original = {
  name: "John",
  age: 30,
  address: {
    city: "New York",
    coordinates: {
      lat: 40.7128,
      lng: -74.006,
    },
  },
  hobbies: ["reading", "coding"],
  joined: new Date("2020-01-01"),
};

const cloned = deepClone(original);
cloned.address.city = "Los Angeles";

console.log(original.address.city); // "New York" (未改变)
console.log(cloned.address.city); // "Los Angeles"

递归优化

1. 尾递归优化

尾递归是指递归调用是函数的最后一个操作:

// ❌ 非尾递归 - 递归调用后还有操作(乘法)
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1); // 还需要做乘法
}

// ✅ 尾递归 - 递归调用是最后的操作
function factorialTail(n, accumulator = 1) {
  if (n === 0) return accumulator;
  return factorialTail(n - 1, n * accumulator); // 最后的操作
}

console.log(factorialTail(5)); // 120

尾递归的优势在于可以被编译器优化为迭代, 不会增加调用栈。

2. 蹦床函数(Trampoline)

JavaScript 目前不保证尾递归优化, 可以用蹦床函数模拟:

// 蹦床函数
function trampoline(fn) {
  return function (...args) {
    let result = fn(...args);

    while (typeof result === "function") {
      result = result();
    }

    return result;
  };
}

// 改造成蹦床版本的斐波那契
function fibTrampoline(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;

  // 返回一个函数而不是直接递归
  return () => fibTrampoline(n - 1, b, a + b);
}

const fib = trampoline(fibTrampoline);
console.log(fib(10)); // 55
console.log(fib(1000)); // 可以处理大数字而不爆栈

3. 记忆化递归

通过缓存避免重复计算:

function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

// 记忆化斐波那契
const fibonacci = memoize(function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

console.time("fib(40)");
console.log(fibonacci(40)); // 102334155
console.timeEnd("fib(40)"); // 几毫秒

// 对比未优化版本
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

console.time("fibSlow(40)");
console.log(fibSlow(40)); // 102334155
console.timeEnd("fibSlow(40)"); // 几秒钟!

递归的实际应用

1. 排列组合

// 生成数组的所有排列
function permutations(arr) {
  // 基础情况: 空数组或单元素数组
  if (arr.length <= 1) {
    return [arr];
  }

  const result = [];

  // 对每个元素作为首元素
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];

    // 递归获取剩余元素的排列
    const remainingPerms = permutations(remaining);

    // 将当前元素加到每个排列前面
    for (const perm of remainingPerms) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

// 生成组合
function combinations(arr, k) {
  // 基础情况
  if (k === 0) return [[]];
  if (arr.length === 0) return [];

  const [first, ...rest] = arr;

  // 包含第一个元素的组合
  const withFirst = combinations(rest, k - 1).map((combo) => [first, ...combo]);

  // 不包含第一个元素的组合
  const withoutFirst = combinations(rest, k);

  return [...withFirst, ...withoutFirst];
}

console.log(combinations([1, 2, 3, 4], 2));
// [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

2. 快速排序

function quickSort(arr) {
  // 基础情况: 空数组或单元素数组已排序
  if (arr.length <= 1) {
    return arr;
  }

  // 选择基准值(这里选中间元素)
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];

  // 分区
  const left = [];
  const equal = [];
  const right = [];

  for (const item of arr) {
    if (item < pivot) {
      left.push(item);
    } else if (item === pivot) {
      equal.push(item);
    } else {
      right.push(item);
    }
  }

  // 递归排序左右分区, 然后合并
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(quickSort(numbers));
// [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

3. 路径查找

// 在迷宫中查找路径
function findPath(maze, start, end, path = [], visited = new Set()) {
  const [x, y] = start;
  const [endX, endY] = end;
  const key = `${x},${y}`;

  // 越界或访问过
  if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) {
    return null;
  }
  if (maze[x][y] === 1 || visited.has(key)) {
    return null;
  }

  // 找到终点
  if (x === endX && y === endY) {
    return [...path, [x, y]];
  }

  // 标记为已访问
  visited.add(key);
  const newPath = [...path, [x, y]];

  // 尝试四个方向
  const directions = [
    [x + 1, y], // 下
    [x - 1, y], // 上
    [x, y + 1], // 右
    [x, y - 1], // 左
  ];

  for (const [nextX, nextY] of directions) {
    const result = findPath(
      maze,
      [nextX, nextY],
      end,
      newPath,
      new Set(visited)
    );

    if (result) {
      return result;
    }
  }

  return null;
}

// 迷宫: 0 = 路, 1 = 墙
const maze = [
  [0, 0, 1, 0],
  [0, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 0, 0, 0],
];

const path = findPath(maze, [0, 0], [3, 3]);
console.log("路径:", path);

何时使用递归

递归适合以下场景:

1. 树形结构: DOM 遍历、文件系统、JSON 操作
2. 分治算法: 快速排序、归并排序、二分查找
3. 回溯问题: 迷宫、八皇后、数独
4. 数学问题: 阶乘、斐波那契、组合
5. 自相似问题: 分形、递归图形

递归不适合的场景:

1. 简单循环: 用 for/while 更简单
2. 深度很大: 可能栈溢出
3. 性能要求高: 函数调用开销较大

小结

递归是一种强大的编程技术, 它让我们能够:

1. 用简洁的代码解决复杂问题: 特别是树形和分治问题
2. 更接近数学定义: 递归版本通常更易理解
3. 优雅地处理自相似结构: 如树、图、分形

但也要注意:

• 确保有明确的基础情况, 避免无限递归
• 考虑性能, 必要时使用记忆化或改为迭代
• 注意调用栈深度限制

掌握递归思维, 会让你在处理复杂问题时有全新的视角和工具。

---