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递归案例内容请搜索开心学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持开心学习网!
- python操作json库(Python将json文件写入ES数据库的方法)
- 禁止鼠标右键的JS代码
- js原生tab栏切换(JavaScript实现简易tab栏切换案例)
- extjs 日期控件
- nodejs的广播机制(node.js如何自定义实现一个EventEmitter)
- js数字时钟编程(JavaScript实现动态数字时钟)
- nodejs数据采集(nodejs获取表单数据的三种方法实例)
- js操作iframe
- html5长图拖动(html5 拖拽及用 js 实现拖拽功能的示例代码)
- js图片水印库(js给图片打马赛克的方法示例)
- js怎么上传压缩图片(如何用JS有效的压缩图片)
- JS中对象的属性
- next js上线(Next.js入门使用教程)
- js判断是否为手机访问
- js实现继承的五种(JavaScript继承的三种方法实例)
- extjs中apply和applyIf的用法
- 被鉴定的古董价值300万 当心,你可能遇到诈骗了(被鉴定的古董价值300万)
- 英语难学吗(初中英语难学吗)
- 如何追女孩子(如何追女孩子的技巧和方法)
- 是不是快乐全被你拿走了(而是你得到的)
- 世界上只有妈妈好(世界上只有妈妈好的歌词)
- 为什么现在社会越来越卷了(现在社会为什么发展那么快呢)
热门推荐
- SQL中PIVOT 行列转换
- 云虚拟主机和普通虚拟主机的区别(云主机为什么要比虚拟主机贵?)
- python常用列表函数和方法(Python enumerate函数功能与用法示例)
- nginx结构图解(详解Nginx 工作原理)
- css3怎么构建阴影(详解css3 mask遮罩实现一些特效)
- dedecms怎么加入模板(dedecms 列表页标题修改图文方法利于优化)
- mysql添加注释视图(mysql创建表添加字段注释的实现方法)
- linux安装sqlserver 2008 r2(Ubuntu 下安装SQL Server教程)
- css基线实例详解(移动端使用 rem 单位时 css sprites 定位问题的解决)
- css3设置过渡效果(CSS3 media queries + jQuery实现响应式导航)