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递归案例内容请搜索开心学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持开心学习网!
- extjs中Toolbar工具栏
- Extjs中文乱码
- Json序列化对象的部分属性值
- thinkphp框架实例(ThinkPHP框架整合微信支付之JSAPI模式图文详解)
- mysql中json的支持(MySQL中json字段的操作方法)
- js使用递归解析(关于JavaScript递归经典案例题详析)
- js网站前端效果(JS如何让你的移动端交互体验更加优秀)
- docker node 分阶段构建(Docker安装、创建镜像、加载并运行NodeJS程序的详细过程)
- JS中call和apply区别
- jsp实现短信验证码(手动实现js短信验证码输入框)
- 最全js面试题(JavaScript必看的10道面试题总结推荐)
- php加密平台(PHP7实现和CryptoJS的AES加密方式互通示例AES-128-ECB加密)
- php 结果集转json(PHP的JSON封装、转变及输出操作示例)
- js条件语句教学(浅谈JS如何写出漂亮的条件表达式)
- extjs多选下拉框
- js如何实现定时器功能(js实现0ms延时定时器的几种方式)
- 浙江省一个县,人口超40万,建县历史超1100年(浙江省一个县人口超40万)
- 五代十国南唐历代国君(五代十国南唐历代国君)
- 飞机引进工程师杨隆 匠人匠心,只争朝夕(飞机引进工程师杨隆)
- 三人行,她们是育人路上的 铁三角 团队(她们是育人路上的)
- 阴阳师 孟婆山兔CP不倒 新皮肤草稿 孟婆兔 让痒痒鼠点赞(阴阳师孟婆山兔CP不倒)
- 阴阳师孟婆御魂推荐 孟婆御魂搭配毕业套(阴阳师孟婆御魂推荐)
热门推荐
- 让文字居中代码是多少(如何使定义了高度和宽度的< a >里的文字垂直居中实现代码)
- sql分析命令(详解SQL中的DQL查询语言)
- linux中基本操作系统有什么(Linux操作系统的概述与简介)
- iframe嵌入页面高度自动适应
- 云主机越来越受欢迎吗(云主机的发展前景怎样?会成为主流吗?)
- docker创建mysql环境(docker上部署MySQL的示例)
- thinkphp5.1手动连接mysql数据库(thinkphp5框架结合mysql实现微信登录和自定义分享链接与图文功能示例)
- 远程给docker容器执行命令(Docker命令让普通用户能够执行的实现)
- sublime text 安装package control,方便其它插件安装
- 表空间不足无法登录(System表空间不足的报警问题浅析)