js使用递归解析(关于JavaScript递归经典案例题详析)
js使用递归解析
关于JavaScript递归经典案例题详析目录
- 什么是递归,它是如何工作的?
- 一、求和
- (1)数字求和
- (2)数组求和
- 二、数据转树
- 三、汉诺塔
- 四、斐波那契数列
- 总结
我们先来看一下递归(recursion)的定义:
递归是一种解决问题的有效方法,在递归过程中,函数将自身作为子例程调用。
简单说程序调用自身的编程技巧叫递归。递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题,问题被拆解成子问题后,递归调用继续进行,直到子问题无需进一步递归就可以解决的地步为止。
使用递归需要避免出现死循环,为了确保递归正确工作,递归程序应该包含2个属性:
- 基本情况(bottom cases),基本情况用于保证程序调用及时返回,不在继续递归,保证了程序可终止。
- 递推关系(recurrentce relation),可将所有其他情况拆分到基本案例。
函数中自己调用自己就是递归,切记要有终止条件,不然进入死循环
一、求和(1)数字求和
function sum(n){ if(n===1){ return n=1 } return n+sum(n-1) } console.log(sum(5));
执行顺序
5+sum(n-1)
5+4+sum(n-1)
5+4+3+sum(n-1)
5+4+3+2sum(n-1)
5+4+3+2+1
(2)数组求和
function sum(arr) { var len = arr.length if (len == 0) { return 0 } else if (len == 1) { return arr[0] } else { return arr[0] + sum(arr.slice(1)) } } let arr = [ 1, 2, 3, 4, 5 ] console.log(sum(arr))
执行顺序
二、数据转树1+sum(2,3,4,5)
1+2+sum(3,4,5)
1+2+3(4,5)
1+2+3+4+sum(5)
1+2+3+4+5
1+2+3+9
1+2+12
1+14
15
let data = [{ id: "01", pid: "", "name": "老王" }, { id: "02", pid: "01", "name": "小张" } ]
function fn(data, rootId = '') { const children = [] //定义一个空数组 data.forEach(item => { if (item.pid === rootId) { //如果每一项的pid=rootId就添加到数组里 children.push(item) item.children = fn(data, item.id) } }); return children }
使用递归转树 要知道根的pid是什么值才能进行下一步操作,作为起点。
执行顺序
三、汉诺塔规则 下面三个柱子分别设为 a 、b、 c、 目标把a中的所有盘子分别从大到小依次放到c柱子中,每次只能移动一个盘子
实现思路:
- 将n-1个盘子从a挪到b
- 将n盘子从a挪到c
- 将n-1个盘子从b挪到c
function fn(num, start, middle, end) { if(num>0){ fn(num-1,start,end,middle) console.log(start+'====>'+end); fn(num-1,middle,start,end) } } fn(2,'a','b','c')
把 num作为盘子的数量 start 作为a盘子 middle作为b盘子 end作为c盘子
例如 2个盘子的执行顺序
1.第一行 把2带进去 num>0 执行第一个函数fn(2-1,start,end,middle) 又去执行了fn(1-1,start,end,middle) 发现num不大于0不仅如此if条件,回过来看 fn(2-1,start,end,middle) ,输出 console.log(a===>b)
2.第二行console.log(start+'====>'+end); 直接输出 a===>c
3.第三行 fn(2-1,middle,start,end) 执行 console.log(b===>c) 下次再去执行 fn(1-1,middle,start,end) 进入不了循环执行完毕
执行顺序有点抽象,实在不理解就按照最简单的思路去做 fn(num, start, middle, end) ,平常我们玩游戏怎么玩就去怎么做,初始图
fn(num-1,start,middle,end) 把 第二个的参数位置作为要移动的盘子 把第四个的参数位置作为移动目标 每次看图把这个公式带进去
第一步 fn(num-1,start,end,middle) 例如两个盘子 肯定是先把a-1放到b上
第二步 把盘子a放c上直接输出 console.log('a===>c')
第三步 把盘子b放c上 fn(num-1,middle,start,end,)
四、斐波那契数列斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、
function Fibonacci(n) { return n <= 1?1:Fibonacci(n - 1) + Fibonacci(n - 2) }
除了前两个 每次都是前一个数和前两个数的和相加等于第三个数
例如数字5举例 前一项是3 前两项是2 3+2=5
总结到此这篇关于JavaScript递归经典案例题详析的文章就介绍到这了,更多相关JavaScript递归案例内容请搜索开心学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持开心学习网!
- js事件冒泡与事件捕获(基于事件冒泡、事件捕获和事件委托详解)
- js使用canvas(JavaScript canvas实现七彩时钟效果)
- js实现自动轮播(原生js封装无缝轮播功能)
- nodejs 内部模块代码(详解Node.js如何处理ES6模块)
- js日期格式化
- nodejsweb服务(Nodejs实现内网穿透服务)
- vscode react jsx语法 开发环境(React-vscode使用jsx语法的问题及解决方法)
- js音乐脚本怎么做(js实现网页音乐播放器)
- js获取微信版本号
- js中substring的用法、与substr的区别
- js开发工具图解(浅谈前端JS沙箱实现的几种方式)
- js中作用域
- laravel 数据表格(Laravel自定义 封装便捷返回Json数据格式的引用方法)
- js获取子表单所有数据(JavaScript实现异步提交表单数据)
- js实现string.format 字符串占位符
- json的语法
- 冰岛旅游攻略(冰岛旅游攻略及花费八日游)
- 寒假旅游攻略(成都寒假旅游攻略)
- 菲律宾旅游攻略(菲律宾旅游攻略地图)
- 清华大学难考吗(清华大学考研录取分数线)
- 观花盆栽佛肚竹盆景制作及养护(观花盆栽佛肚竹盆景制作及养护)
- 春天养佛肚竹,做好这几件事,叶绿根壮寓意好 越养越旺家(春天养佛肚竹做好这几件事)
热门推荐
- mysql删库操作记录(mysql常用sql与命令之从入门到删库跑路)
- http状态码304的含义(网站出现HTTP 300 Multiple Choices是什么意思?怎么处理?)
- python实例教程(Python魔法方法详解)
- iis的安装与配置图解教程(windows+IIS6安装及搭建网站服务器环境教程)
- docker的常用的命令(Docker 清理命令集锦)
- 泛型中new()约束
- ps如何画一个哆啦a梦(CSS画出一个可爱神奇的多啦A梦)
- vue怎么使用element(Vue Element前端应用开发之图标的维护和使用)
- Tomcat和Weblogic部署纯html文件过程解析(Tomcat和Weblogic部署纯html文件过程解析)
- html5input标签的默认属性(移动端HTML5 input常见问题小结)