1递归含义:在某时某刻某个条件下调用包含自己的函数
2:注意点:⑴递归过程中一定要加限制条件,要不然会陷入死循环:
死循环eg:
function f(someP){
f(somP);
}
f(4); //Uncaught RangeError: Maximum call stack size exceeded
正常调用:
//计算输入某个正整数,然后一直向下叠加 ,这里仅仅做一个简单示例,不进行输入num的判断
function f(num){
let x;
if(num>0){
x =num + f(num-1);
return x;
}
return false;
}
f(5);
递归有个过程,不是一步到位的,这一点尤其重要,因为在学习JS数据结构与算法中的二叉搜索树的移除代码会至关重要,不懂递归过程的话很容易看不懂移除代码
function getSum(num){
if(x === 1){
return 1;
}
return num + getSum(num-1)
}
getSum(5);
过程如下:
①:getSum(5)调用函数并传入参数5,执行函数中的num +getSum(num-1) ->5+getSum(5-1)
②:getSum(4)调用函数并传入参数4,执行函数中的num+getSum(num-1) ->4+getSum(4-1)
③:getSum(3)调用函数并传入参数3,执行函数中的num+getSum(num-1) ->3+getSum(3-1)
④:getSum(2)调用函数并传入参数2,执行函数中的num+getSum(num-1) ->2+getSum(2-1)
⑤:getSum(1)调用函数并传入参数1,执行函数中的return 1;
⑥:这时候再一步一步往回走,即1+2+3+4+5;即可以理解为递归调用过程中,是不会立即计算的,要等到限制条件结束后,才会一步一步往上计算。
3:二叉搜索树的移除节点:移除节点程序是二叉搜索树程序方法中最复杂的一个。
eg:
class Node{ //节点类
constructor(key){
this.key = key;
this.left = null;
this.right = null;
}
}
function defaultCompare(a, b) { //比较函数
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
};
class BinarySearchTree{
constructor(compareFn = defaultCompare){
this.compareFn = compareFn;
this.root = null;
}
remove(key){
this.root = this.removeNode(this.root,key);
}
removeNode(node,key){
if(node == null){
return null;
}
if(this.compareFn(key,node.key) === Compare.LESS_THAN){ // (1)
node.left = this.removeNode(node.left,key); //(2)
return node; //(3)
}else if (this.compareFn(key,node.key) === Compare.BIGGER_THAN){ //(4)
node.right = this.removeNode(node.right,key); //(5)
return node; //(6)
}else{ //(7)
if(node.left == null && node.right == null){ //(8) //第一种情况,移除一个叶节点(只有父节点没有子节点的节点)
node = null; //(9)
return node; //(10)
}
if(node.left == null){ //第二种情况,移除有一个左or右子节点的节点
node = node.right; //(11)
return node; //(12)
}else if(node.right == null) {
node = node.left; //(13)
return node; //(14)
}
const aux = this.minNode(node.right); //(15) //第三种情况,移除有两个子节点的节点
node.key = aux.key; //(16)
node.right = this.removeNode(node.right,aux.key); //(17)
return node; //(18)
}
}
}
const tree1 = new BinarySearchTree();
tree1.remove(8);
假设现在有一个节点顺序为
现在我们需要移除节点8,则代码的顺序应该是:
①:开始时key:8 node: Node{ key: 11, left : Node, right : Node},进入行(1),判断大小后进入行(2),此时key:8 node: Node{ key: 7, left : Node, right : Node}
②:递归调用第一次,进入行(4)判断大小后进入行(5),此时key:8 node: Node{ key: 9, left : Node, right : Node}
③:递归调用第二次,进入行(1)判断大小后进入行(2),此时key:8 node: Node{ key: 8, left : null, right : null}
④:递归调用第三次,进入行(7 ,8, 9),返回一个node,此时key: 8 ,node :null;
⑤:进入行(3),此时结果为: key:8 ,node:Node{key: 9 ,left:null,right:Node};
⑥:进入行(6),此时结果为: key:8 ,node:Node{key: 9 ,left:Node,right:Node};
⑦:进入行(3),此时结果为:key:8 ,node:Node{key: 11,left:Node,right:Node};
⑧:返回到remove()后,跳出程序,节点8已移除。
备注1:上述步骤只实现了第一种情况,如果有需要,读者可以用chrome的调试工具进行断点调试,在Sources中可查看key及node的具体情况,
备注2:这里很明显说明了递归调用的执行顺序
在js中通过如果一个函数直接或间接调用函数本身,则该函数称为递归函数。
JavaScript生成树形菜单需求:首先这是一个数据集—js的类型,我们需要把生成一个tree形式的对象 : id,与pid之间的对应关系,当pid不存在,或pid:0的时候,这一项,应该为树的顶端,那么我们需要去重新建一次索引。
什么是递归组件?简单来说就是在组件中内使用组件本身,下面我们就来看看如何在项目中使用递归组件去解决我们上面问题。类似与信息分类的展示在我们的项目中是非常常见的形式,我们利用递归组件可以很好的去解决问题
最近遇到一个需求,平时被后台惯着直接返回了树形结构给到前端,前端对这种嵌套类型的数据(如地区的级联或菜单的树形结构)省掉了一层处理。换了个后台开发返回了扁平化的数组数据给到前端自己去处理如下data。突然有点慌......
循环数组或对象内每一项值,在 js 里原生已经提供了一个迭代器。凡是需要用到递归的函数参考迭代器模式,能写出更优雅,可读性更高的代码。
递归函数是在一个函数通过名字调用自身的情况下构成的,这种写法在函数有名字,而且名字以后也不会变的情况下是没有问题的。但是函数的执行与函数名factorial紧紧耦合在了一起
递归:你打开面前这扇门,看到屋里面还有一扇门(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开
由于父元素的定位属性, 导致子元素及其孙元素等的offsetLeft和offsetTop变得和预期不一致(预期上都是到屏幕左边和上边的位置), 由于需要做鼠标拖动旋转和鼠标框选
项目中有一个需求,一个tabBar下面如果没有内容就不让该tabBar显示,当然至于有没有内容,需要我们通过请求的来判断,但是由于请求是异步的,如何让请求按照tabBar的顺序进行?
所谓递归,就是既有传递,又有回归,与其说是传递与回归,初学不如理解是一种 “循序递进”与“规律约束”。为什么这样说,因为递归算法相比较于循环在代码结构方面个人认为更加简洁清晰,清晰易懂,递归注重的是一种有序的规律
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!