JavaScript递归算法中的数组引用陷阱：理解深浅拷贝在集合生成中的应用

1. 递归生成集合的基础与常见问题

在计算机科学中，生成一个集合的所有子集是一个经典的组合问题，常通过递归（回溯）算法来解决。其核心思想是对于集合中的每个元素，我们都可以选择“包含”它或“不包含”它。

以下是一个典型的JavaScript实现尝试：

var subsets = function(nums = [1, 2, 3]) {
    nums.sort((a, b) => a - b); // 排序有助于处理重复元素或保持结果有序，此处非核心问题点
    return dfs(nums, 0, [], []);
};

var dfs = function(nums, pos, tmp, res) {
    // 递归终止条件：当所有元素都已考虑完毕
    if (nums.length === pos) {
        // 问题发生点：直接推送 tmp
        // res.push(tmp); // ❌ 错误做法
        res.push(tmp.slice()); // ✅ 正确做法
        return;
    }

    // 1. 选择当前元素 nums[pos]
    tmp.push(nums[pos]);
    dfs(nums, pos + 1, tmp, res);

    // 2. 不选择当前元素 nums[pos]
    tmp.pop(); // 回溯：移除之前添加的元素，以便探索不包含它的路径
    dfs(nums, pos + 1, tmp, res);

    return res;
}

console.log(subsets()); // 期望输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

当代码中 res.push(tmp); 被执行时，开发者可能会发现最终 console.log(subsets()); 输出的结果是一个包含多个空数组的数组，而非预期的所有子集。然而，如果将 res.push(tmp); 改为 res.push(tmp.slice());，代码就能正常工作。更令人困惑的是，如果在递归终止条件处同时打印 tmp 和 tmp.slice()，它们在当前时刻的值看起来是相同的。这究竟是为什么？

2. 深入理解JavaScript的数组引用

问题的根源在于JavaScript中数组（以及所有对象）的“引用传递”特性。当我们将一个数组赋值给另一个变量，或者将一个数组作为参数传递给函数时，实际上是传递了该数组在内存中的地址（引用），而不是数组的实际内容（值）。

立即学习“Java免费学习笔记（深入）”；

让我们通过一个比喻来理解： 想象 tmp 是一个“购物袋”。当 dfs 函数递归调用时，tmp 这个购物袋会被重复使用。

• tmp.push(nums[pos])：往购物袋里放入一个商品。
• tmp.pop()：从购物袋里取出一个商品。

当执行到 res.push(tmp); 时，res 数组实际上存储的是这个“购物袋”的引用，而不是购物袋里那一刻商品的“快照”。这意味着，res 中的所有元素都指向同一个 tmp 购物袋。

随着递归的深入和回溯，tmp 购物袋里的商品会不断变化。当所有递归调用完成，dfs 函数的执行栈清空，tmp 数组最终会被 pop() 操作清空。此时，res 中存储的所有引用都指向了这个已经被清空的 tmp 购物袋。因此，当你最终查看 res 的内容时，看到的是多个指向同一个空购物袋的引用，所以结果看起来都是空数组。

而 console.log(tmp); 之所以能打印出当前 tmp 的正确内容，是因为 console.log 在执行的那一刻会去读取 tmp 引用所指向的内存地址中的内容并打印出来。它只反映了瞬时状态，而 res.push(tmp) 则是将一个动态变化的引用存储起来。

3. 解决方案：利用浅拷贝创建独立快照

为了解决这个问题，我们需要在将 tmp 加入 res 之前，创建一个 tmp 的独立副本（即“快照”），然后将这个副本的引用存入 res。这样，即使 tmp 在后续的递归中发生变化，res 中存储的副本也不会受到影响。

JavaScript提供了几种创建数组浅拷贝的方法：

AppMall应用商店

AI应用商店，提供即时交付、按需付费的人工智能应用服务

56

查看详情

3.1 Array.prototype.slice() 方法

slice() 方法返回一个数组的浅拷贝。当不带任何参数调用时，它会从头到尾复制整个数组。

// ... (之前的 subsets 和 dfs 定义不变)

var dfs = function(nums, pos, tmp, res) {
    if (nums.length === pos) {
        // 使用 slice() 创建 tmp 的浅拷贝
        res.push(tmp.slice()); // ✅ 正确做法
        return;
    }

    tmp.push(nums[pos]);
    dfs(nums, pos + 1, tmp, res);

    tmp.pop();
    dfs(nums, pos + 1, tmp, res);

    return res;
}

console.log(subsets()); // 输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

此时，res.push(tmp.slice()); 将 tmp 在当前状态下的一个独立副本推入 res，这个副本与 tmp 不再关联，后续 tmp 的变化不会影响已保存的副本。

3.2 展开运算符（Spread Syntax）[...]

ES6 引入的展开运算符 (...) 提供了另一种简洁且常用的创建数组浅拷贝的方式。

// ... (之前的 subsets 和 dfs 定义不变)

var dfs = function(nums, pos, tmp, res) {
    if (nums.length === pos) {
        // 使用展开运算符创建 tmp 的浅拷贝
        res.push([...tmp]); // ✅ 另一种正确做法
        return;
    }

    tmp.push(nums[pos]);
    dfs(nums, pos + 1, tmp, res);

    tmp.pop();
    dfs(nums, pos + 1, tmp, res);

    return res;
}

console.log(subsets()); // 输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

[...tmp] 会创建一个新的数组，并将 tmp 中的所有元素“展开”到这个新数组中，从而实现浅拷贝。

4. 注意事项与最佳实践

• 理解引用与值： 这是JavaScript中一个非常基础但又极其重要的概念。基本数据类型（如字符串、数字、布尔值、null、undefined、Symbol、BigInt）是按值传递的，而对象（包括数组、函数、普通对象）是按引用传递的。在处理对象时，尤其是在需要保留对象不同状态的场景下，务必注意这一点。

• 浅拷贝与深拷贝： slice() 和展开运算符 (...) 都执行的是浅拷贝。这意味着如果数组 tmp 的元素本身也是引用类型（例如，tmp 是一个包含其他数组或对象的数组），那么浅拷贝只会复制这些内部引用，而不会复制内部引用指向的实际对象。如果内部对象也可能在后续操作中被修改，且你需要保存它们的独立副本，那么就需要进行深拷贝（例如，使用 JSON.parse(JSON.stringify(obj)) 这种简单粗暴的方式，或者更专业的库如 Lodash 的 _.cloneDeep()）。在本例中，nums 数组的元素是数字，属于基本数据类型，因此浅拷贝已足够。

• 回溯算法中的常见模式： 在回溯算法中，tmp 数组（或类似的路径/状态记录变量）通常是可变的，并且在递归调用前后进行修改（添加/移除元素）。因此，在将 tmp 的当前状态保存到结果集时，几乎总是需要进行浅拷贝，以确保保存的是一个独立的“快照”。

5. 总结

在JavaScript的递归算法，特别是涉及构建集合（如子集、排列、组合）的场景中，理解数组的引用传递特性至关重要。直接将可变数组的引用添加到结果集中，会导致最终结果被修改为空。通过使用 Array.prototype.slice() 或展开运算符 [...] 进行浅拷贝，我们可以确保将当前状态的独立副本保存下来，从而获得正确的预期输出。掌握这一技巧，是编写健壮、可预测的JavaScript递归代码的关键一步。

以上就是JavaScript递归算法中的数组引用陷阱：理解深浅拷贝在集合生成中的应用的详细内容，更多请关注php中文网其它相关文章！