js终止递归

2024-06-05 13:28

文章标签 js 递归终止

本文主要是介绍js终止递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

终止递归

1. 实现目标：js 编写递归方法查找指定节点；

2. 需解决问题：找到所需节点后，递归不会终止，直到所有节点遍历完成后才会停止，会消耗性能

3. 解决方案：优化递归方法，在找到所需节点后，直接终止递归

4. 代码：

// 假设我们有一个简单的树节点结构
function TreeNode(value, children = []) {this.value = value;this.children = children;
}// 创建示例树
const root = new TreeNode(1, [new TreeNode(2, [new TreeNode(4), new TreeNode(5)]),new TreeNode(3, [new TreeNode(6),new TreeNode(7, [new TreeNode(8), new TreeNode(9)]),]),
]);
// 错误写法（该写法虽然能找到正确节点，但找到正确节点后还是会遍历后续节点，对于某些"洁癖患者"来说不能容忍，而且需要定义外部变量不够优雅）
let result = null;
// 递归遍历树的函数
function traverseTreeErr(findVal, node = root) {console.log("traverseTreeErr", node); // 打印这里就可以知道 找到对应节点后，会继续遍历子节点// 检查当前节点的值是否匹配if (node.value === findVal) {result = node;return;}// 遍历子节点for (let child of node.children) {traverseTreeErr(findVal, child); // 递归调用}
}
traverseTreeErr(6);
console.log("traverseTreeErr.result", result);
// 正确写法（该写法 不需要定义外部变量且找到所需节点后立即终止了递归）
// 递归遍历树的函数
function traverseTree(findVal, node = root) {console.log("traverseTree", node);// 检查当前节点的值是否匹配if (node.value === findVal) {return node;}// 遍历子节点for (let child of node.children) {let result = traverseTree(findVal, child); // 递归调用if (result) {// 如果找到了匹配的节点，返回它return result;}}// 如果没有找到匹配的节点，返回nullreturn null;
}
// 调用traverseTree来查找值为3的节点
console.log("traverseTree.result", traverseTree(6)); // 应该输出值为6的TreeNode对象