一、递归与回溯：从思想到模板

递归和回溯，说实话是算法面试里最让人又爱又恨的题型。爱的是——代码写出来特别优雅，几行就能解决看似复杂的问题；恨的是——理解起来确实有点绕，稍不留神就陷入无限递归的深渊。

我个人习惯把递归看作「俄罗斯套娃」：一个大娃娃里面装着一个稍小的娃娃，小的里面还有更小的……直到最小的那个不能再拆了，然后一层层往回组装。嗯，这个比喻虽然老套，但确实贴切。

1.1 递归三要素

我在项目中遇到过不少递归写崩的情况，后来总结出一个规律：只要抓住三个核心要素，递归就不会跑偏。

说白了，写递归就是回答三个问题：「什么时候停？」「怎么往下走？」「回来怎么拼？」

来看一个最经典的例子——计算阶乘：

// 递归求 n!
function factorial(n) {
    // 1. 终止条件：0! = 1
    if (n === 0) return 1;
    
    // 2. 递推关系：n! = n * (n-1)!
    // 3. 返回值处理：直接相乘
    return n * factorial(n - 1);
}

你想想看，这个函数执行的时候发生了什么？factorial(5) 等着 factorial(4) 的结果，factorial(4) 等着 factorial(3)……一直等到 factorial(0) 直接返回 1，然后一层层往回乘。这就是递归的「递」和「归」。

1.2 回溯算法框架

回溯，说白了就是「走不通就回头」的递归。它和普通递归的区别在于：回溯会尝试所有可能的路径，走不通就撤销选择，换一条路继续试。

我曾经在面试中被问到「全排列」问题，当时脑子一热直接写了 5 层 for 循环……后来面试官笑着说：「你试试回溯？」我才意识到，回溯就是专门解决这类「多阶段决策」问题的利器。

回溯算法的核心框架，我习惯这样记：

function backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    
    for (选择 in 选择列表) {
        // 做选择
        路径.add(选择);
        
        // 进入下一层决策树
        backtrack(路径, 选择列表);
        
        // 撤销选择（回溯的核心！）
        路径.remove(选择);
    }
}

这个框架里，最关键的就是最后一步——撤销选择。为什么？因为你不撤销，下一轮循环用的就是被污染过的路径，结果全乱套了。

1.3 剪枝优化：让回溯跑得更快

剪枝，顾名思义就是把决策树上那些「肯定没结果」的分支提前砍掉。我刚开始学回溯时，经常不剪枝，结果跑一个 N=10 的 N 皇后问题，等了半分钟没出结果……后来加了剪枝，秒出。

常见的剪枝策略有：

• 可行性剪枝——当前选择已经不满足约束条件，直接跳过
• 最优性剪枝——当前路径已经比已知最优解差，不用继续了
• 重复性剪枝——相同状态已经搜索过，用备忘录记下来避免重复

举个例子，全排列中如果数组有重复数字，不加剪枝就会产生大量重复排列。这时候加一句 if (used[i] || (i > 0 && nums[i] === nums[i-1] && !used[i-1])) continue; 就能砍掉一半的搜索空间。

1.4 经典例题：全排列

全排列是回溯的「Hello World」。题目很简单：给定一个不含重复数字的数组，返回所有可能的排列。

function permute(nums) {
    const result = [];
    const path = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack() {
        // 终止条件：路径长度等于数组长度
        if (path.length === nums.length) {
            result.push([...path]);  // 注意要拷贝！
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;  // 剪枝：已经用过的数字跳过
            
            // 做选择
            path.push(nums[i]);
            used[i] = true;
            
            // 递归
            backtrack();
            
            // 撤销选择
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return result;
}

这里有个坑我踩过——result.push([...path]) 如果不拷贝，后面 path.pop() 会把结果数组里的内容也改掉。因为 JavaScript 数组是引用类型，你存的是引用，不是值。

1.5 经典例题：N 皇后

N 皇后问题，说白了就是「在 N×N 的棋盘上放 N 个皇后，让它们互相攻击不到」。攻击规则很简单：同一行、同一列、同一对角线上不能有两个皇后。

这个问题的回溯解法，核心在于如何快速判断当前位置是否安全。我习惯用三个数组来记录：

• cols：记录哪些列已经被占用
• diag1：记录主对角线（行-列）是否被占用
• diag2：记录副对角线（行+列）是否被占用

function solveNQueens(n) {
    const result = [];
    const board = new Array(n).fill(null).map(() => new Array(n).fill('.'));
    const cols = new Set();
    const diag1 = new Set();  // 行 - 列
    const diag2 = new Set();  // 行 + 列
    
    function backtrack(row) {
        // 所有行都放完了，找到一个解
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            // 剪枝：检查当前位置是否安全
            if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
                continue;
            }
            
            // 做选择
            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            
            // 递归下一行
            backtrack(row + 1);
            
            // 撤销选择
            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }
    
    backtrack(0);
    return result;
}

为什么用 row - col 和 row + col 来标识对角线？你想想看，在同一主对角线上的格子，行和列的差值是一个常数；在同一副对角线上的格子，行和列的和是一个常数。这个规律记住了，N 皇后问题的核心就抓住了。

1.6 知识体系总览

下面这张图总结了递归与回溯的核心知识结构，我建议你把它记在脑子里：

1.7 小结

递归和回溯，说白了就是「有策略地穷举」。递归帮我们优雅地描述问题，回溯帮我们系统地搜索解空间，剪枝则让搜索变得高效。

我个人觉得，学回溯最好的方式就是多画递归树。把决策树画出来，你就能清楚地看到：哪些分支是必走的，哪些是可以砍掉的。画着画着，你就有了「剪枝直觉」——看到一个问题，本能地知道哪里可以优化。

最后送你一句话：递归是思想，回溯是方法，剪枝是艺术。三者结合，你就能解决一大类「看似复杂、实则套路」的算法题。

---

公众号:蓝海资料掘金营，微信deep3321