个人理解：递归就是自己调用自己。递归需要一个条件，如果条件不满足他会继续执行，条件满足，递归返回
ps：回头使用调试工具，看看递归是怎么一步一步执行的。
1. 剖析利用递归算法，求斐波那契数列
1、1、2、3、5、8、13、21... //第n个月有几对兔子，可以让前两个月的兔子数相加
2. 利用递归实现深拷贝
function clone(target) { if (typeof target === 'object') { //如果target是复杂类型的话， let cloneTarget = Array.isArray(target) ? [] : {}; //再次判断，是数组还是对象，并用cloneTarget保存 for (const key in target) { //遍历传进来的数据 cloneTarget[key] 是数组或对象的属性名 = cloneTarget[key] = clone(target[key]); } return cloneTarget; } else { return target; } };
3. 利用递归将数组转成树结构
流程如下：
1.首先传入两个参数，一个是数组，一个是要查询的pid
2.进入函数，首先遍历数组，进行判断，看看这个要查询的pid
和数组中的parentId一样不，如果一样，说明他有上级
3.使用递归，将这个要查询的pid的id当做刚开始的要查询的pid
查询，再进入递归，查询他们有没有下属，有的话加入到
直到没有下属为止，
const arr = [ {id:1, parentId: null, name: 'a'}, {id:2, parentId: null, name: 'b'}, {id:3, parentId: 1, name: 'c'}, {id:4, parentId: 2, name: 'd'}, {id:5, parentId: 1, name: 'e'}, {id:6, parentId: 3, name: 'f'}, {id:7, parentId: 4, name: 'g'}, {id:8, parentId: 7, name: 'h'}, ]
//需要插入父节点id，pid为null或''，就是找root节点，然后root节点再去找自己的子节点 //代码提取版： function array2Tree(data, pid){ let res = []; data.forEach(item => { if(item.parentId === pid){ let itemChildren = array2Tree(data,item.id); if(itemChildren.length) item.children = itemChildren; res.push(item); } }); return res; }
const arr = [ {id:1, parentId: null, name: 'a'}, {id:2, parentId: null, name: 'b'}, {id:3, parentId: 1, name: 'c'}, {id:4, parentId: 2, name: 'd'}, {id:5, parentId: 1, name: 'e'}, 思考过程版： {id:6, parentId: 3, name: 'f'}, 1.首先传入两个参数，一个是数组，一个是要查询的pid {id:7, parentId: 4, name: 'g'}, 2.进入函数，首先遍历数组，进行判断，看看这个要查询的pid {id:8, parentId: 7, name: 'h'}, 和数组中的parentId一样不，如果一样，说明他有上级 ] 3.使用递归，将这个要查询的pid的id当做刚开始的要查询的pid 查询，再进入递归，查询他们有没有下属，有的话加入到 直到没有下属为止， //需要插入父节点id，pid为null或''，就是找root节点，然后root节点再去找自己的子节点 //先找他们有没有上级，根据parentID，接着找他们自己有没有下级 //总体流程是：先传一个pid,找pid等于pid的，找到了。再调函数，以这个pid当id，看看arr里面谁的pid等于id的 function array2Tree(data, pid){ let res = []; data.forEach(item => { //遍历原数据，item代表每一个对象 if(item.parentId === pid){ // 如果传过来的pid,有上级。下面是递归，一直往上找上级 let itemChildren = array2Tree(data,item.id);//这句话是上级的id，定义变量接收 if(itemChildren.length) item.children = itemChildren;//如果 res.push(item); } }); return res } let oop = array2Tree(arr,1) console.log(oop)
4. 利用递归将数组转成树结构 （2）
利用递归将数组转成树结构 *有问题 optionData(data) { console.log('开始转换为树形数据'); let cloneData = JSON.parse(JSON.stringify(data)); // 对源数据深度克隆 return cloneData.filter(father => { // 循环所有项，并添加children属性 let branchArr = cloneData.filter(child => father.value == child.parentId); // 返回每一项的子级数组 branchArr.length > 0 ? father.children = branchArr : ''; //给父级添加一个children属性，并赋值 return father.parentId == 0; //返回第一层 }); }, //将查询到的list转为树形 let treedata = this.optionData(data);
5 利用递归求数组之和
总体思路分为两步：
第一步，写出口条件：这里的重点是利用数组的长度作为递归出口。长度为1 的时候递归出去
第二步，写递归条件：首先，递归是自己调用自己，必须得出去，不然死循环。那么，怎么让数组的长度变短呢？需要给一个条件，比如刚开始数组长度是5，那么他应该是第二次比第一次短，是4，然后3、2、1。最后等于1的时候递归就可以出去了。可以使用slice（）方法，他的作用是返回一个新数组，里面两个参数，第一个是必须得从哪里开始，第二个是可选哪里结束，这里只需要利用第一个，从1开始，这样每次返回的新数组都会少一个，直至剩下一个，递归结束。
var arr = [1,5,2] function f(arr){ var len = arr.length //定义数组的长度 if(len === 0){ //递归出口1 return 0 }else if(len === 1){ //递归出口1 return arr[0] }else{ return arr[0] + f(arr.slice(1)) //slice可以返回一个新数组，这个数组从下标第一个开始执行 } return a } var d = f(arr) console.log(d);
6.利用递归解决汉罗塔问题
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
思路：
将A柱子上的n-1个盘子暂时移到B柱子上
A柱子只剩下最大的盘子，把它移到目标柱子C上
最后再将B柱子上的n-1个盘子移到目标柱子C上
人话：
把A上n-1个盘子通过借助辅助塔（C塔）移到了B上
把最大的一个盘子由A移到C上去
把B上n-1个盘子通过借助辅助塔（A塔）移到了C上
var index = 0; function hanoi(num,A,B,C){ index++; if(num==1){ //柱子只底下只有一个盘子 move(A,C) }else{ //A的num-1个盘子通过C移动到B hanoi(num-1,A,C,B); //A的最底下的盘子移动到C move(A,C) //B的盘子通过A移动到C hanoi(num-1,B,A,C) } } function move(first,final){ console.log('从',first,' 移动到 ',final); } hanoi(4,'第一根柱子','第二根柱子','第三根柱子'); console.log('一共移动了',index,'次');
