递归啊，很多人学起来觉得玄乎，其实它就像那种俄罗斯套娃，一个娃娃里面装着另一个娃娃。你要想把所有娃娃都拆开，得有一个最小号娃娃作为“终点”。这个“最小号娃娃”放到递归里，就是基准条件。基准条件设计得好，递归函数健壮又清晰；设计不好，轻则逻辑错乱，重则让浏览器直接崩溃。

数学归纳法是高中就学过的证明方法。它核心就两步：第一步，证明某个命题在最小的基础情况上成立；第二步，假设命题在n成立，然后证明在n+1也成立。这两步合起来，就能推出所有自然数都成立。递归函数的写法几乎一模一样：先处理最小的输入，这是基准条件；再假设递归调用已经解决了比当前输入更小的问题，然后基于这个结果拼出当前问题的答案，这是递归步骤。

1.1 数学归纳法到底在干嘛

比如要证明“从1加到n的和等于n(n+1)/2”。首先检查n=1，左边1，右边1*2/2=1，成立。然后假设n=k时成立，即1+...+k=k(k+1)/2，接着证明n=k+1时也成立：1+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2，正好就是n=k+1时的公式。这样一来，从1推到2，从2推到3，无穷无尽都成立。这就是数学归纳法的力量。

1.2 递归函数和归纳法的对应关系

递归函数里，基准条件就好比“n=1时成立”的证明，它给出了递归的停止点。递归步骤就好比“从k推到k+1”的证明，它把大问题化成小问题。只要这两个部分都正确，整个递归函数就正确。所以，设计递归函数时，真正需要深入思考的，就是基准条件该怎么选、怎么保证它正确。

二、基准条件该怎么设计

很多新手写递归，会纠结“递归式怎么写”，却忘了最要命的其实是基准条件。基准条件一旦错了，整个递归就成了无底洞。接下来我来拆几个核心原则。

2.1 原则一：基准条件要选“最简单、不能再拆”的情况

以计算阶乘为例。n!在数学上的定义是：n! = n * (n-1)!，而0! = 1。注意，这里0! = 1就是一个不能再拆的最小情况。如果只写n>0的情况，基准条件选成n==1，也能工作；但选成0!更符合阶乘的数学定义，也更自然。代码如下：

// 技术栈：JavaScript
// 计算n的阶乘（n >= 0）
function factorial(n) {
  // 基准条件：0! 定义为 1，这是整个递归的出口
  if (n === 0) {
    return 1;
  }
  // 递归步骤：n! = n * (n-1)!
  // 这里factorial(n-1)是“已经算好的小问题”
  return n * factorial(n - 1);
}

// 测试一下
console.log(factorial(5)); // 期望输出 120

你看，基准条件写得清楚，递归步骤直接搬数学公式就行，基本不会错。反过来，如果把基准条件漏掉，这个函数就会一直往负数方向递归，直到栈溢出。

2.2 原则二：基准条件要覆盖所有“出口”

有些递归问题不是只有一个基准条件，而是有两个甚至多个。最典型的例子是斐波那契数列。它的定义是：F(0)=0，F(1)=1，当n>=2时，F(n)=F(n-1)+F(n-2)。这里必须同时把F(0)和F(1)都作为基准条件，缺一个都不行。如果只写F(0)，那么当n=1时，会执行递归调用F(0)和F(-1)，而F(-1)又需要F(-2)，完全乱套。看代码：

// 技术栈：JavaScript
// 计算斐波那契数列第n项
function fib(n) {
  // 基准条件1：F(0) = 0
  if (n === 0) {
    return 0;
  }
  // 基准条件2：F(1) = 1
  if (n === 1) {
    return 1;
  }
  // 递归步骤：F(n) = F(n-1) + F(n-2)
  return fib(n - 1) + fib(n - 2);
}

// 测试前几项：0, 1, 1, 2, 3, 5, 8...
console.log(fib(6)); // 期望输出 8

这个例子提醒我们，在动手写基准条件前，先把这个递归问题的“最小输入集”全列出来。比如斐波那契的最小输入就是0和1，数组求和的最小输入是空数组，链表长度的最小输入是空链表。多想想“输入还能不能再小”，就能避免漏掉出口。

2.3 原则三：基准条件的返回值要符合“归纳定义”

这个原则听起来抽象，其实很简单：基准条件返回的值，必须能让递归步骤在边界上也成立。我拿数组求和举例。我们定义“数组arr下标从0到len-1的和”为：如果数组长度是0，和就是0；如果长度大于0，和等于第一个元素加上剩余元素的和。这个定义里，空数组的“和”就是0，这就是符合归纳定义的基准条件。看代码：

// 技术栈：JavaScript
// 递归计算数组所有元素之和
function sum(arr) {
  // 基准条件：空数组的和就是0
  if (arr.length === 0) {
    return 0;
  }
  // 递归步骤：第一个元素 + 剩余元素的和
  // 每次调用数组长度都减1，一定能走到空数组
  return arr[0] + sum(arr.slice(1));
}

// 测试
console.log(sum([1, 2, 3, 4])); // 期望输出 10
console.log(sum([]));           // 期望输出 0

你看，空数组返回0，这个0在“第一个元素 + 剩余元素的和”里充当了加法运算的单位元，不会影响结果。如果是求乘积，空数组的乘积应该返回1，因为1是乘法运算的单位元。所以基准条件的返回值，要和递归步骤里的运算性质匹配。这就是“归纳定义”的含义。

2.4 原则四：基准条件要保证“递归能收敛”

“收敛”这个词听着高级，其实就是每次递归调用，都要让问题规模向基准条件靠拢。如果问题规模不缩小，基准条件就永远等不到。来看一个错误例子：

// 技术栈：JavaScript
// 错误示范：没有让问题规模减小，会无限递归
function badReverse(s) {
  // 本来想反转字符串，但这里没有基准条件
  // 每次递归都把第一个字符放到最后，但字符串长度根本没变
  return badReverse(s.slice(1) + s[0]);
}

这段代码里，传入的字符串长度永远是原来的长度，所以递归永远停不下来。正确的做法是：当字符串长度小于等于1时，直接返回它；否则，把第一个字符放到剩余字符串的反转结果之后。每次递归调用长度都会减1，最终到达长度0或1的基准条件。修正后的代码如下：

// 技术栈：JavaScript
// 反转字符串
function reverse(str) {
  // 基准条件：空字符串或单个字符，反转后还是自己
  if (str.length <= 1) {
    return str;
  }
  // 递归步骤：把第一个字符放在最后面
  // 剩余字符串的长度每次减少1
  return reverse(str.slice(1)) + str[0];
}

// 测试
console.log(reverse("hello")); // 期望输出 "olleh"

所以每次写递归步骤时，要问自己一句话：这个递归调用比当前输入“小”在哪？如果回答不出来，说明递归步骤写错了。

三、从数学归纳法到递归的实操步骤

光知道原则还不够，关键是怎么动手。我建议按下面四步走，每一步都对应数学归纳法的一部分。

3.1 第一步：把要解决的问题写成数学定义

先别急着写代码，用自然语言或数学公式把问题定义清楚。比如“判断一个字符串是不是回文”，可以定义为：空字符串或长度为1的字符串是回文；如果长度大于等于2，那么首尾相同，并且去掉首尾后剩下的子串也是回文。有了这个定义，递归结构就自然出来了。

3.2 第二步：在定义里找出所有“最小输入”

上面的定义里，最小输入就是空字符串和长度为1的字符串。这两个情况不需要递归，直接返回true。注意，可能有两个基准条件，都要写。

3.3 第三步：把定义里的“递归描述”改写成递归调用

首尾相同，并且剩余子串是回文，那么整个字符串就是回文。这一步对应数学归纳法里的“假设小规模成立，推导大规模成立”。

3.4 第四步：把基准条件和递归步骤组合，并测试边界

组合起来，再试几个例子：空字符串、单个字符、双字符、奇偶长度、包含空格等。完成后的代码如下：

// 技术栈：JavaScript
// 判断字符串s是否为回文
function isPalindrome(s) {
  // 基准条件1：空字符串是回文
  if (s.length === 0) {
    return true;
  }
  // 基准条件2：单个字符是回文
  if (s.length === 1) {
    return true;
  }
  // 递归步骤：首尾相同，且去掉首尾后的子串也是回文
  if (s[0] !== s[s.length - 1]) {
    return false;
  }
  return isPalindrome(s.slice(1, -1));
}

// 测试
console.log(isPalindrome("a"));       // true
console.log(isPalindrome("ab"));      // false
console.log(isPalindrome("aba"));     // true
console.log(isPalindrome("racecar")); // true

你看，整个函数写起来非常“顺”，因为它就是按数学归纳法的骨架来的。先有基准，再有归纳，最后自然就是完美的递归。

四、常见陷阱与进阶技巧

4.1 基准条件的顺序会影响逻辑吗

一般来说，基准条件之间是“或”的关系，顺序不影响结果。但有些场景下，非法输入要在递归之前先拦下来。比如阶乘函数要求n非负，如果你直接把负数扔进去，基准条件永远不成立，就会死循环。所以要在函数开头加一个参数校验：

// 技术栈：JavaScript
function safeFactorial(n) {
  // 参数校验：负数直接抛错，避免无限递归
  if (n < 0) {
    throw new Error("n必须大于等于0");
  }
  if (n === 0) {
    return 1;
  }
  return n * safeFactorial(n - 1);
}

这种防御性写法不算破坏基准条件，而是给递归加了一层安全锁。设计健壮的递归函数，参数校验是必不可少的一环。

4.2 递归深度和栈溢出

每次递归调用都会在调用栈里占一块空间。如果递归深度太深，比如几万层，浏览器或Node.js会直接报错。就算基准条件再正确，也扛不住深度太大。这时候有两个常见的处理思路：改成尾递归，或者用迭代代替递归。尾递归的意思是，递归调用是函数的最后一个动作，不依赖递归结果做任何运算。看一个例子：

// 技术栈：JavaScript
// 尾递归：用额外的参数来“累积”结果
function safeSum(arr, index = 0, total = 0) {
  // 基准条件：当index到达数组末尾时，返回累计值
  if (index === arr.length) {
    return total;
  }
  // 递归步骤：累加当前元素，index+1
  // 注意递归调用是函数的最后一步，没有做任何额外运算
  return safeSum(arr, index + 1, total + arr[index]);
}

// 测试
console.log(safeSum([1, 2, 3, 4, 5], 0, 0)); // 期望输出 15

当然，并不是所有JavaScript引擎都会优化尾递归，但是这种写法至少让逻辑更贴近“循环”的思考方式。如果深度真的可能特别大，最好直接用普通循环，比如用for循环累加。

4.3 利用缓存优化重复计算

斐波那契的朴素递归重复计算了很多子问题，效率极低。可以用一个缓存对象把已经算过的结果存起来，下次直接取。这也是动态规划思想的一部分。看代码：

// 技术栈：JavaScript
const cache = {};

function fibWithCache(n) {
  // 基准条件不变
  if (n === 0) return 0;
  if (n === 1) return 1;
  // 如果缓存里有，直接返回，不再递归
  if (cache[n] !== undefined) {
    return cache[n];
  }
  // 递归计算，并把结果存入缓存
  cache[n] = fibWithCache(n - 1) + fibWithCache(n - 2);
  return cache[n];
}

// 测试
console.log(fibWithCache(50)); // 瞬间出结果，而朴素递归会非常慢

注意这里的缓存对象放在全局，实际项目中要放到函数内部或者使用闭包，避免污染。这个技巧不是递归特有的，但对于“树形递归”特别有效。

五、应用场景与优缺点

5.1 应用场景

递归在编程里到处都是。最常见的场景是遍历树数据结构，比如DOM树、文件目录、组织结构。二叉树的先序、中序、后序遍历，写起来用递归简直不要太舒服。分治算法（归并排序、快速排序）也是递归思想的应用。还有回溯算法，比如八皇后问题、走迷宫，本质上也是递归加状态恢复。另外，递归适合解决“自相似”的问题，比如汉诺塔、括号匹配、表达式解析等。你只要发现一个问题可以写成“先处理一小步，剩余部分用同样方法处理”，递归就可以上。

5.2 优缺点

递归的优点非常明显：代码简洁、可读性强、和数学定义高度一致。它把复杂的逻辑拆成了“基准”和“归纳”两个清晰的部分，调试起来心不累。但缺点也逃不掉：每次函数调用都要压栈，性能和内存开销比循环大；递归深度有限，处理不好就爆栈；写不好还会陷入无限递归。所以递归适合“逻辑优先”的场景，如果性能要求苛刻，或者数据规模巨大，就得考虑改成迭代或尾递归优化。

六、注意事项与总结

最后再啰嗦几句注意事项。第一，写基准条件之前，一定把最小输入找全，不要凭感觉写。第二，保证每次递归调用都在向基准靠近，最好在纸上模拟两三次调用过程。第三，别忘了处理非法参数，避免负数、空值等把递归带进深渊。第四，复杂递归用缓存优化，别让同一个子问题反复算。第五，如果递归深度深得离谱，果断换迭代写法，不要跟调用栈硬刚。

递归其实一点也不神秘。你把它拆成两件事：一是找到一个可靠的“最小号娃娃”，二是把“从大号娃娃拆到小号娃娃”的步骤写清楚。这两件事分别对应数学归纳法的基础步骤和归纳步骤。基准条件设计得好，递归函数就像一棵根系扎实的树，枝繁叶茂也不会倒。希望这篇文章能让你下次写递归时，心里先想着数学归纳法，再动手指头。