企业网站模板2016成套,免费注册入口,网络服务器租赁费一般多少钱,国内做设计的网站建设大家好#xff0c;我是若川。持续组织了5个月源码共读活动#xff0c;感兴趣的可以点此加我微信 ruochuan12 参与#xff0c;每周大家一起学习200行左右的源码#xff0c;共同进步。同时极力推荐订阅我写的《学习源码整体架构系列》 包含20余篇源码文章。对于大部分前端(包… 大家好我是若川。持续组织了5个月源码共读活动感兴趣的可以点此加我微信 ruochuan12 参与每周大家一起学习200行左右的源码共同进步。同时极力推荐订阅我写的《学习源码整体架构系列》 包含20余篇源码文章。对于大部分前端(包括我)接触到递归的时候就是学函数的时候对于递归的认知就是函数自己调用自己然后给函数定义一个出口通过这个函数将一件的事情拆分成同类型的小事情。但你会发现你写的递归情况很少因为很多情况下递归是可以用循环去实现同样的效果那对于递归具体使用场景什么时候需要用递归就是本文主要想探讨的话题。递归只能去解决树形结构的问题吗对于很少使用递归来解决问题的很容易就会把递归想成只有树形情况才能使用递归下面我们先通过解决树形情况深入了解递归能解决哪些场景的问题以及除了树形结构的数据它还能处理什么问题「问题一」获取根节点名称点击当前节点获取根级节点的名称这里用element的el-tree组件来做测试根级节点不包括tree中的虚拟根节点指的是数据的根节点这就是虚拟根节点实现的效果是这样的这个需求很简单我们很容易就想到了递归为什么?获取根级不停的获取当前节点的上级至到没有上级就是根级递归出口条件通过node.parent或者node.level递归中变化的状态值node.parentgetRootNodeName(node) {if (!node) returnif (node.level 1) {return node.label}return this.getRootNodeName(node.parent)
}通过上面三个条件我们实现了这个递归函数这里需要注意的是递归中变化的状态值这个是整个递归中最难理解也最重要的部分后文会展开来讲这种递归其实很易就能写出来循环就只能实现一样的效果getRootNodeName(node) {if (!node) returnwhile (node.level 1) {node node.parent}return node.label
}「问题二」获取当前节点所在树的指定层级节点 这里有还有个约束条件node节点中没有level属性了只有parent属性指向节点的父节点这里为了更好的表达我们把node节点的中的虚拟根节点去除。我们要实现这样的效果点击当前节点获取当前节点所在的层级递归实现getNodeLevel(node) {if (!node.parent) return 1return this.getNodeLevel(node.parent) 1
}当前这个递归函数主要实现思路就是在不停的递进当node.parent不存在就说明当前节点是一级节点然后在回溯的过程中在上级节点的层级 1 当前节点层级递归你打开面前这扇门看到屋里面还有一扇门。你走过去发现手中的钥匙还可以打开它你推开门发现里面还有一扇门你继续打开它。若干次之后你打开面前的门后发现只有一间屋子没有门了。然后你开始原路返回每走回一间屋子你数一次走到入口的时候你可以回答出你用这把钥匙打开了几扇门。循环实现getNodeLevel(node) {let n 1let p nodewhile (p.parent) {p p.parentn}return n
}循环你打开面前这扇门看到屋里面还有一扇门。你走过去发现手中的钥匙还可以打开它你推开门发现里面还有一扇门若前面两扇门都一样那么这扇门和前两扇门也一样如果第二扇门比第一扇门小那么这扇门也比第二扇门小你继续打开这扇门一直这样继续下去直到打开所有的门。但是入口处的人始终等不到你回去告诉他答案上面两段话其实就很好的说出了递归和循环之间的差别就是因为循环没有回溯的过程我们当前的循环就不得不存储每个递归的状态值数据「问题三」: 树节点的过滤有人可能会问树节点的过滤这个在el-tree的用例中不就有吗但是那个并不能解决我们实际场景的问题举个例子来看下el-tree...:filter-node-methodfilterNode
/script
export default {methods: {filterNode(value, data) {if (!value) return truereturn data.label.indexOf(value) ! -1},}
}
/script存在的问题当前的过滤只是通过label包含的方式把不符合的节点全都过滤掉了而我们想要的效果应该是过滤不符合条件的分支如果符合当前层级符合条件那它的下级就不应该过滤掉递归实现methods: {filterNodeMethod(value, data, node) {if (!value) {return true}return this.deepfilterChildNode(value, node)},deepfilterChildNode(value, node) {if (node.level 1) return falseconst { filterNodeByIndexOf, deepfilterChildNode } thisif (filterNodeByIndexOf(node.label, value)) {return true}return deepfilterChildNode(value, node.parent)},filterNodeByIndexOf(label, value) {return label.indexOf(value) ! -1}
}循环实现主要实现函数就是deepfilterChildNode, 接着再用循环来实现下同步的效果methods: {deepfilterChildNode(value, node) {const { filterNodeByIndexOf } thisif (filterNodeByIndexOf(node.label, value)) {return true}// 一级节点没有父级if (node.level 1) return false// 往上找到最大那个节点结束const maxNode 1 // 多级节点父级符合条件不要、过滤子级let parentNode node.parentwhile (parentNode.level maxNode) {if (filterNodeByIndexOf(parentNode.label, value)) {return true}parentNode parentNode.parent}// 当前节点的最大父节点都没找到return false},
}「问题四」实现instanceof作用判断右边构造函数的原型对象是否存在于左边对象的原型链上原理左侧的原型链中存在右侧的原型对象左侧必须是对象1 instaceof Number // false
Number(1) instaceof Number // false
new Number(1) instaceof Number // true右侧必须是构造函数let f1 () {};
let f2 function () {}
class f3 {}
obj instanceof f1; // 报错
obj instanceof f2 // false
obj instanceof f3 // false左侧的原型链中存在右侧的原型对象let obj {}
class ctor {}
console.log(obj instanceof ctor); // false
Object.setPrototypeOf(obj, new ctor)
console.log(obj instanceof ctor); // truelet getProto Object.getPrototypeOf
getProto(getProto(obj)) ctor.prototype // true递归实现function _instaceof(obj, ctor) {// 左边必须是对象if (!(obj typeof obj object)) {return false}// 获取对象的原型链对象let proto Object.getPrototypeOf(obj)// 判断对象的原型链对象是否是构造函数函数的原型对象return proto ctor.prototype || _instaceof(proto, ctor)
}循环实现function instanceOf1(obj, ctor) {if (!(obj typeof obj object)) {return false}let proto while(proto Object.getPrototypeOf(obj)) {if (Object.is(proto, ctor.prototype)) return trueobj proto}return false
}「问题五」深度属性测试数据let obj {a: {b: {c: 1,cc: {dd: {f: f Val}}}},data: {v1: v1,v2: v2,v3: v3}
}获取属性function getDeepObjAttr(obj, deepPath) {const deepGet (o, paths) {if (!paths.length) return oreturn deepGet(Reflect.get(o, paths.shift()), paths)}return deepGet(obj, deepPath.split(.))
}console.log(getDeepObjAttr(obj, a.b.cc.dd.f)) // f Val设置属性function setDeepObjAttr(model, deepPath, val) {let paths deepPath.split(.)if (!paths.length) return modelconst setDeep (o, p, i) {if (i 0) return olet prop p[i]// 最后一层要设定的值if (i p.length - 1) {Reflect.set(o, prop, val)} else {Reflect.set(o, prop, {...getDeepObjAttr(model, p.slice(0, i 1).join(.)),...o})Reflect.deleteProperty(o, paths[i 1])}return setDeep(o, p, --i)}return Object.assign(model,setDeep({}, [...paths], paths.length - 1))
}setDeepObjAttr(obj, a.b.c, 2)
setDeepObjAttr(obj, a.b.cc.dd.f, f Val21)改变后的obj{a: {b: {c: 2,cc: {dd: {f: f Val21}}}},data: {v1: v11,v2: v2,v3: v3}
}这个递归有多个出口条件且并不是在单纯的做一件类型事情且递归函数中引用的自由变量(全局变量model递归过程中如果修改model其他递归中的变量也会受影响对于递归那些状态值(变量)需要提取到全局可以这样思考类似于盗梦空间我手里有10块钱我做了第一个梦(n)在这个梦中我花了2块接着又做了一个梦(n 1), 在n1中我还是有10块钱前面梦中花掉的钱并不影响我这个梦中的钱。那这个状态值(变量)就是递归函数内部创建的局部变量反之就需要把状态值(变量)放到全局这里同样给出循环的实现function getDeepObjAttr(obj, deepPath) {let paths deepPath.split(.)if (!paths.length) return objlet prop,targetVal,tempObj objwhile ((prop paths.shift()) paths.length) {if (!Reflect.has(tempObj, prop)) {return}tempObj tempObj[prop]}return tempObj[prop]
}function setDeepObjAttr(model, deepPath, val) {// 路径let paths deepPath.split(.)// 目标值存放符合路径下的所有属性let targetVal {}// 用于查找每个对象的proplet pathsNew paths.concat([])let propfor (let i paths.length - 1, j i; i 0; i--) {prop paths[i]// 最后一层要设定的值if (i j) {targetVal[prop] val} else if (i 0) {// 第一层需要直接替换第一个属性const obj this.getDeepObjAttr(model, prop);Reflect.set(model, prop, Object.assign({}, obj, targetVal))} else {// 更新每一个层级的值(去除存起来的值)let curDeppObj getDeepObjAttr(model, pathsNew.join(.))// 将当前层级的值存储起来Reflect.set(targetVal, prop, Object.assign({}, curDeppObj, targetVal))// 删除上个路径存储的值Reflect.deleteProperty(targetVal, paths[i 1])}// 将处理过的路径去除pathsNew.pop()}return model
}对于递归是否只能解决树形结构的问题还没有给出答案又出现了一个问题递归和循环的区别递归和循环有什么区别 通过上面的五个例子我们发现递归和循环都能实现其实递归与循环是两种不同的解决问题的典型思路 都具有相同的特性即做重复任务 。 单从算法设计上看递归和循环并无优劣之别。然而在实际开发中因为函数调用的开销递归常常会带来性能问题特别是在求解规模不确定的情况下而循环因为没有函数调用开销所以效率会比递归高。插一句求解规模不确定还包含隐示的数据规模很大但前端页面很少会碰到处理数据规模特别大的情况所以用递归也没啥问题相同点将大事件拆分成小事情即**重复任务 **循环、递归调用处理过程中将状态值变换即状态展开区别如果使用循环我们就得建立堆栈来替代系统栈保存处理当前状态的内容(变量)再次认识递归let arr [1, 2, 3, 4, 5, 6]function logArr(arr) {for (let i 0; i arr.length; i) {console.log(arr[i]);}
}
logArr(arr)让你依次打印输出中的每一项这个能用递归实现吗先想想答案是肯定可以function logArr(arr) {const dfs (idx) {if (idx arr.length) returnconsole.log(arr[idx]);dfs(idx 1)}dfs(0)
}斐波纳契数列斐波纳契数列指的是这样一个数列1、1、2、3、5、8、13、21简单来讲就是从第二个数之后的每个数是前两个数之和 F00F11FnF(n-1)F(n-2)n2递归求解function fibonacci(n) {// 递归终止条件if (n 2) {return 1}// 相同重复逻辑缩小问题的规模return fibonacci(n - 1) fibonacci(n - 2)
}fibonacci(5)状态展开生成树这里面包含了许多重复计算计算fib(5)时1次fib(4)
2次fib(3)
3次fib(2)
5次fib(1)
3次fib(0)像这种重复的计算就相当于相同的分支在dfs(深度优先搜索)中有个很重要的操作叫做剪枝; 在当前递归的实现中那些重复的计算我们可以进行缓存当后面出现重复计算就不再调用也算是剪枝这对于递归是很大的性能优化。// 创建一个空对象,作为缓存的容器
let cache {};
function fibonacci(n) {if (n 1 || n 2) {return 1;}if (cache[n]) {return cache[n];}return cache[n] fibonacci(n - 1) fibonacci(n - 2);
}还有一种缓存的方案在递归的过程中进行计算回溯的时候把最后的结果返回function fibonacci(n, cur 0, next 1) {if(n 0) return 0;if(n 1) return next; return fibonacci(n - 1, next, cur next);
}循环求解function fibonacci(n) {if (n 2) return 1// 维护栈的状态值,以便状态回溯let first 1// 维护栈的状态值,以便状态回溯let second 1let ret 0n - 2while (n--) {// 当前数 前一个数 前两个数ret first secondfirst secondsecond ret}return ret
}现在可以回答第一个问题了递归不是只能去解决树形数据结构和明显的上下级关系的数据对这种情况的数据是非常符合递归的定义所以我们很容易能想像出来像斐波纳契数列 、 阶乘 、杨辉三角..., 这种通过递推可以求解的方式也可以用递归通过递归过程中变化状态值来求解答案。二分查找循环实现function binarySearch(nums, target) {let l 0let r nums.length - 1let midwhile (l r) {mid (l r) 1if (nums[mid] target) {return mid} else if (nums[mid] target) {r mid - 1} else {l mid 1}}return -1
}递归实现变换状态值状态展开生成树function binarySearch(nums, target, l 0, r nums.length - 1) {let midwhile (l r) {mid (l r) 1if (nums[mid] target) {return mid} else if (nums[mid] target) {return binarySearch(nums, target, l, mid - 1)} else {return binarySearch(nums, target, mid 1, r)}}return -1
}算法中递归的应用 在算法中对于递归的应用场景特别特别多dfs回溯、二叉树遍历、翻转、路径总和...把以上这些类型的题用递归刷几题对于递归就会有更深的认知和理解后面碰到的需求如果可以用递归解自然你就能想到递归。现在给出一些递归可解的leetcode题并不是说去学算法刷题这里的目的是做这些题可以让我们对于用递归有更深入的了解递归用的不太多的可能需要花点时间全都掌握之后对自己也是个提升二叉树遍历二叉树有三种遍历方式前序遍历根、左、右中序遍历左、根、右后续遍历左、右、根前序遍历leetcode144. 二叉树的前序遍历/*** param {TreeNode} root* return {number[]}*/
var preorderTraversal function(root) {let ans []const preIterator (root) {if (!root) returnans.push(root.val)preIterator(root.left)preIterator(root.right)}preIterator(root)return ans
}中序遍历leetcode94. 二叉树的中序遍历/*** param {TreeNode} root* return {number[]}*/
var inorderTraversal function(root) {let ans []const inIterator (root) {if (!root) returninIterator(root.left)ans.push(root.val)inIterator(root.right)}inIterator(root)return ans
};后序遍历leetcode145. 二叉树的后序遍历/*** param {TreeNode} root* return {number[]}*/
var postorderTraversal function(root) {let ans []const postIterator (root) {if (!root) returnif (!postIterator(root.left)) {if (!postIterator(root.right)) {ans.push(root.val)}}}postIterator(root)return ans
};路径总和leetcode112. 路径总和var hasPathSum function (root, targetSum) {if (!root) return falsetargetSum targetSum - root.val// 当前节点是叶子节点if (!root.left !root.right) {// 如果当前节点刚好能符合所有ragetSum, 表示当前节点就是目标节点return targetSum 0}return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum)
};leetcode113. 路径总和 II/*** param {TreeNode} root* param {number} targetSum* return {number[][]}*/
var pathSum function (root, targetSum) {let ans []const dfs (root, targetSum, temp []) {if (!root) returntemp.push(root.val)targetSum - root.valif (!root.left !root.right targetSum 0) {ans.push([...temp])}dfs(root.left, targetSum, temp)dfs(root.right, targetSum, temp)temp.pop()}dfs(root, targetSum)return ans
};回溯leetcode39. 组合总和/*** param {number[]} candidates* param {number} target* return {number[][]}*/var combinationSum function (candidates, target) {const ans []const dfs (idx, target, temp []) {if (idx candidates.length) returnif (target 0) returnif (target 0) {ans.push([...temp])temp []return}temp.push(candidates[idx])dfs(idx, target - candidates[idx], temp)temp.pop()dfs(idx 1, target, temp)}dfs(0, target)return ans
};写在最后 业精于勤荒于嬉如果文章中有那块写的不太好或有问题欢迎大家指出我也会在后面的文章不停修改。也希望自己进步的同时能跟你们一起成长。喜欢我文章的朋友们也可以关注一下我会很感激第一批关注我的人。此时年轻的我和你轻装上阵而后富裕的你和我满载而归。················· 若川简介 ·················你好我是若川毕业于江西高校。现在是一名前端开发“工程师”。写有《学习源码整体架构系列》20余篇在知乎、掘金收获超百万阅读。从2014年起每年都会写一篇年度总结已经写了7篇点击查看年度总结。同时最近组织了源码共读活动帮助3000前端人学会看源码。公众号愿景帮助5年内前端人走向前列。识别上方二维码加我微信、拉你进源码共读群今日话题略。分享、收藏、点赞、在看我的文章就是对我最大的支持
