【算法图解】递归入门：函数调用自己的魔法

如果说算法界有一个概念能让初学者瞬间“宕机”，那一定是递归（Recursion）。

很多人对递归的印象就是：“为了理解递归，你首先要理解递归。” 这种无限循环的梗虽然好笑，但确实道出了递归的本质：自己调用自己。

今天，小明就带你拆解这个“魔法”，看看函数是怎么在自己的世界里玩俄罗斯套娃的。

一、什么是递归？

简单来说，递归就是一个函数在它的定义中调用了它自己。

听起来很傻，对吧？就像你对着镜子照镜子，镜子里还有一个你在照镜子……

1.1 一个生活中的例子：找钥匙

想象你在家找一把锁着的盒子的钥匙。

1. 迭代法（循环）：你拿出一大堆小盒子，一个一个打开看。如果里面是钥匙，成功；如果里面还是个盒子，就把这个新盒子放进待检查清单，继续循环。
2. 递归法：你打开一个盒子，如果里面是钥匙，成功；如果里面还是个盒子，你就叫你自己过来，对这个新盒子重复同样的动作。

二、递归的两个核心要素

如果你写了一个递归函数却没写好，结果通常只有一种：栈溢出（Stack Overflow）。

为了防止函数无限地调用下去，每个递归函数必须包含两部分：

2.1 基准情形（Base Case）

也就是“什么时候停止”。如果没有基准情形，函数就会像掉进黑洞一样永远停不下来。

2.2 递归情形（Recursive Case）

也就是“什么时候继续调用自己”。

三、实战：计算阶乘（Factorial）

阶乘是学习递归最经典的例子。5! 就是 5 * 4 * 3 * 2 * 1。

function factorial(n) {
  // 1. 基准情形：当 n 为 1 时，停止递归
  if (n === 1) {
    return 1;
  }
  // 2. 递归情形：n! = n * (n-1)!
  return n * factorial(n - 1);
}

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

3.1 它是怎么运行的？（调用栈图解）

当你调用 factorial(3) 时，内存里发生了什么？

1. 调用 factorial(3)，它说：“等一下，我要先算 3 * factorial(2)”。
2. 调用 factorial(2)，它说：“等一下，我要先算 2 * factorial(1)”。
3. 调用 factorial(1)，它说：“好的，我是 1”。（触发基准情形）
4. factorial(2) 收到 1，算出 2 * 1 = 2。
5. factorial(3) 收到 2，算出 3 * 2 = 6。

这就是“递”进去，“归”出来。

四、递归的优缺点

优点：代码优雅

递归能让复杂的问题（比如树的遍历、汉诺塔）变得异常简洁。代码读起来就像在读数学定义，非常有逼格。

缺点：性能与内存

每次函数调用都会在内存里创建一个“栈帧”（Stack Frame）。如果递归太深，内存就会爆掉。此外，递归通常比循环要慢一些，因为函数调用的开销比跳转指令要大。

总结

1. 递归是函数调用自身的行为。
2. 基准情形是递归的出口，没有它就会死循环。
3. 调用栈记录了每一层递归的状态，它是“递”与“归”的物质基础。
4. 能用循环解决的简单问题，优先用循环；逻辑复杂的结构（如树、图），递归是神器。

小明建议： 初学者理解递归时，不要试图在脑子里追踪几十层的调用记录，那会让你 CPU 烧掉。你只需要专注两点：1. 这一层要做什么？ 2. 什么时候停下来？

“递归最难的地方是什么？” “是理解为什么它居然能跑通。” —— 小明

最后，送你一个冷笑话： 面试官：“请解释一下什么是递归。” 程序员：“如果你给我发 offer，我就告诉你。” 面试官：“那我现在就给你发 offer。” 程序员：“好的。请解释一下什么是递归。” 面试官，卒。