前端递归常见应用

概览

在 JavaScript 中，递归是一种编程技术，指的是函数直接或间接调用自身的过程。
递归通常用于解决可以分解为相同子问题的问题。通过不断地将问题分解成更小的、相似的子问题，直到达到某种基本情况（不再需要进一步递归的简单情况）。

递归一般要满足以下两个关键条件：

1. 存在基本情况（终止条件）：必须有某种简单的情况，在这种情况下递归不再继续进行，避免无限递归导致程序崩溃。
2. 能够不断将问题规模缩小：通过递归调用自身，要能逐步将问题转化为更小的、相似的子问题，直到最终达到基本情况。

一. 常见应用

1. 递归计算阶乘

function factorial(n) {if (n === 0 || n === 1) {return 1;} else {return n * factorial(n - 1);}
}

当递归终止后，从内到外依次执行。

2. 一维数组转成树形结构

const arr = [{id: 4, pid: 3},{id: 'aa', pid: 'a'},{id: 1, pid: null},{id: 3, pid: 2},{id: 'a', pid: 'a0'},{id: 2, pid: 1},{id: 'a0', pid: null}
];function buildTreeData(arr,parentId = null) {const result = [];const rootFilterArray = arr.filter(item => item.pid === parentId);debugger;if(rootFilterArray.length > 0 ) {rootFilterArray.forEach(subitem => {debugger;const children = buildTreeData(arr,subitem.id);if(children.length > 0 ) {subitem.children = children}result.push(subitem)});}return result
}const resData = buildTreeData(arr);
console.log(resData,'resData')

3. 查找树形结构子项

const checkTestData = [{"id": 1,"pid": null,"children": [{"id": 2,"pid": 1,"children": [{"id": 3,"pid": 2,"children": [{"id": 4,"pid": 3,"children": []}]}]}]},{"id": "a0","pid": null,"children": [{"id": "a","pid": "a0","children": [{"id": "aa","pid": "a","children": []}]}]}
]function getItemById(arr,id) {for(let item of arr) {debugger;if(item.id === id) {return item} else if(item.children) {const data = getItemById(item.children,id);if(data) {return data}}}
}const resDataItem = getItemById(checkTestData,3);
console.log(resDataItem,'resDataItem')

二. 总结

关键点梳理：

1. 递归终止条件确定: 即没有调用自身的函数。
2. 递归终止后结果的获取：有的时候直接返回最终的递归结果，有的时候拿到每次递归的结果之后由内至外依次进行逻辑处理。