JavaScript中关于递归与回溯的实例详解
发布网友
发布时间：2024-12-05 01:21
共1个回答
热心网友
时间：2024-12-09 17:40
javascript
function calcNum(n) { let sum = 0 function dfs(n) { if (n > 100) { return } sum += n n++ dfs(n) } dfs(n) return sum }
console.log(calcNum(1)) // 5050
上述代码通过递归逐步求和，直到n超过100为止。回溯则是递归过程的一部分，表现为函数调用栈的撤销。例如，在上述`calcNum`函数中，每次递归调用都会输出当前的n值，而递归返回时，n值会按相反顺序输出。
回溯的概念可以通过二叉树遍历来更好地理解。二叉树的遍历方式包括前序、中序和后序遍历。前序遍历的基本结构如下：
javascript
const treeNode = { val: 1, left: null, right: { val: 2, left: { val: 3, left: null, right: null }, right: null } }
前序遍历的代码实现如下：
javascript
function getRoot(root) { const res = [] function dfs(root) { if (!root) { return } res.push(root.val) dfs(root.left) dfs(root.right) } dfs(root) return res }
console.log(getRoot(root)) // 5 4 1 2 6 7 8
从中序遍历和后序遍历的实现中，可以看出递归的回溯机制在遍历过程中起着关键作用。例如，中序遍历的代码实现如下：
javascript
function getRoot(root) { const res = [] function dfs(root) { if (!root) { return } dfs(root.left) res.push(root.val) dfs(root.right) } dfs(root) return res }
console.log(getRoot(root)) // 1 4 2 5 6 7 8
后序遍历的代码实现如下：
javascript
function getRoot(root) { const res = [] function dfs(root) { if (!root) { return } dfs(root.left) dfs(root.right) res.push(root.val) } dfs(root) return res }
console.log(getRoot(root)) // 1 2 4 7 8 6 5
递归的边界条件确保了递归不会无限执行。例如，在二叉树遍历中，当节点为null时，递归结束。通过这些示例，我们可以看到递归和回溯在解决复杂问题时的强大作用。
实际业务场景中，递归可以用于遍历菜单树或其他树形结构。例如，给定一个树形结构的数据，我们需要遍历每个节点：
javascript
let tree = [ { id: '1', title: '节点1', children: [ { id: '1-1', title: '节点1-1' }, { id: '1-2', title: '节点1-2' } ] }, { id: '2', title: '节点2', children: [ { id: '2-1', title: '节点2-1' } ] } ]
递归遍历节点的代码实现如下：
javascript
function getRootData(tree) { const res = [] function dfs(tree) { if (!tree || tree.length === 0) { return res } for (let i = 0; i tree.length; i++) { const t = tree[i] if (t.children && t.children.length > 0) { dfs(t.children) } else { res.push(t.title) } } } dfs(tree) return res }
console.log(getRootData(tree)) // ['节点1-1', '节点1-2', '节点2-1']
回溯的应用还包括寻找节点的所有父节点。例如，给定一个节点的id，我们需要找到其所有父节点的路径：
javascript
const tree = [ { id: '1', title: '节点1', children: [ {id: '1-1',title: '节点1-1' }, {id: '1-2',title: '节点1-2' } ] }, { id: '2', title: '节点2', children: [ {id: '2-1',title: '节点2-1',children: [ { id: '2-1-1', title: '节点2-1-1' }] } ] } ]
递归查找路径的代码实现如下：
javascript
function pathTree(tree, id) { const res = [] function dfs(tree, path) { if (!tree || tree.length === 0) { return } for (let i = 0; i tree.length; i++) { const t = tree[i] path.push(t.id) if (path.includes(id)) { res.push(path.slice()) } if (t.children && t.children.length > 0) { dfs(t.children, path) } path.pop() } } dfs(tree, []) return res }
console.log(pathTree(tree, '2-1-1')) // [2,2-1,2-1-1]
递归中的`path.pop()`操作用于回溯，确保路径返回到正确的状态。这在处理组合问题时尤为重要，例如从1到4的数字中选择2个数的所有组合：
javascript
function combine(n, k) { const res = [] function dfs(n, path, startIndex) { if (path.length === k) { res.push(path.slice()) return } for (let i = startIndex; i <= n; i++) { path.push(i) dfs(n, path, i + 1) path.pop() } } dfs(n, [], 1) return res }
console.log(combine(4, 2)) // [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
通过递归和回溯，我们可以有效地解决复杂问题。递归不仅简化了代码，还提供了清晰的问题解决思路。希望这些示例能够帮助你更好地理解和应用递归和回溯。
