JS尾递归的实现方法及代码优化技巧
本文实例讲述了JS尾递归的实现方法及代码优化技巧。分享给大家供大家参考,具体如下:
在学习数据结构和算法的时候,我们都知道所有的递归都是可以优化成栈+循环的。
对于特定的递归函数,一般我们都是手动对它们进行优化的。
在学习scala的时候,接触到尾递归的概念。我们只要将递归写成尾递归方式,编译器会自动帮助我们优化。
ps:并不是所有的递归都可以改写成尾递归
在js中,尾递归通常会被解释器优化。然而,并不是所有的js解释器都支持尾递归优化。
对于不支持尾递归优化的环境,我们需要手动将递归优化成栈+循环。
这里实现了一个通用的方法,将尾递归优化成栈+循环。
代码摘自阮一峰的《ECMAScript入门》这本书。
具体代码如下
function tco(f) { var value; var active = false; var accumulated = []; return function accumulator() { accumulated.push(arguments); if(!active) { active = true; while(accumulated.length) { value = f.apply(this, accumulated.shift()); } active = false; return value; } }; } var sum = tco(function(x, y) { if(y > 0) { return sum(x + 1, y - 1); } else { return x; } }); let res = sum(1, 5) console.info(res);
这段代码非常精妙!
分析
已知,任何递归可以写成循环+栈。
实现将任何尾递归转换成循环+栈执行而不需要针对每个尾递归函数写一个实现版本的思路。
困难在于,任何尾递归,通用实现。而不是针对某一个递归函数。
要点:
栈中保存的数据,正是递归函数的参数。
通用实现,那就必须依赖原来的递归函数,循环的终止条件,正是递归的结束条件。
要将递归函数的参数入栈,而不修改原来的递归函数,就必须用一个函数代替递归函数被调用,从而取得函数入参。
递归函数的终止条件,每一个递归函数都不一样,但是如果递归函数没有被再次调用,说明已达到终止条件。即终止条件和递归函数的调用有关联。而递归函数每次调用,都会将参数入栈。所以可以根据栈中是否有元素,推断是否达到终止条件。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
相关推荐
-
JavaScript使用递归和循环实现阶乘的实例代码
[实现方法] 1.利用while循环来做,当然for循环也可以. 2.递归 [代码内容] 偷懒,直接用onkeyup事件来限制来页面的输入 循环代码: //第一种方法 while循环 oCount.onclick = function (){ var oNum = document.getElementById('num').value; oNum = Number(oNum); if(oNum <= 1){ oBox.innerHTML = 1; } var oRes = 1; while(o
-
JavaScript实现JSON合并操作示例【递归深度合并】
本文实例讲述了JavaScript实现JSON合并操作.分享给大家供大家参考,具体如下: 为什么我会想到写这几行代码 在实际工作中,我们会使用许多或自主开发或第三方的工具,有些工具的配置文件相当细节,使用频率低倒也罢了,使用频率高的话必然造成很多代码冗余.所以我都会对这些工具做二次封装,把不经常改动的配置给予默认值.如果需要改动,传入新的配置覆盖原来的配置即可. 起初我以为这是一项很简单的需求 var json1 = { // 固定的配置 a: 1, b: 2, c: 3, } var json
-
javascript如何用递归写一个简单的树形结构示例
现在有一个数据,需要你渲染出对应的列表出来: var data = [ {"id":1}, {"id":2}, {"id":3}, {"id":4}, ]; var str="<ul>"; data.forEach(function(v,i){ str+="<li><span>"+v.id+"</span></li>&
-
JavaScript递归函数解“汉诺塔”算法代码解析
"汉诺塔"是一个著名的益智游戏.塔上有3根柱子和一套直径各不相同的空心圆盘.开始时柱子上的所有圆盘都按照从小到大的顺序堆叠.目标是通过每次移动一个圆盘到另一根柱子,最终把一堆圆盘移动到目标柱子上,过程中不允许把交大的圆盘放置在较小的圆盘之上. 仔细解读这段话,如果有10个圆盘甚至更多,那操作步骤绝对多到让人震惊,但目标是把一堆圆盘移动到目标柱子上,如果把上面的9个圆盘看成一套,第10个圆盘看成另一套,先移动9个圆盘到另一根柱子上,再把上面8个圆盘看成一套,第9个圆盘看成另一套--依次类
-
JavaScript递归算法生成树形菜单
本文实例为大家分享了js生成树形菜单的具体代码,供大家参考,具体内容如下 1.最终效果图(这里仅为实现算法,并加载至页面,不做任何css界面优化) 注释:本示例包含三级目录菜单,但实际上可支持N级(可使用该代码自行测试) 2.数据源 菜单信息一般来源于数据库中数据表,且为自连接表,其中包含主要字段(主键,菜单名称,父级id): 本示例在前端页面中使用对象数组模拟从数据库获取菜单信息: var menuArry = [ { id: 1, name: "办公管理", pid: 0 }, {
-
JavaScript累加、迭代、穷举、递归等常用算法实例小结
本文实例讲述了JavaScript迭代.迭代.穷举.递归等常用算法.分享给大家供大家参考,具体如下: 累加和累积 累加:将一系列的数据加到一个变量里面.最后的得到累加的结果 比如:将1到100的数求累加和 小球从高处落下,每次返回到原来一半,求第十次小球落地时小球走过的路程 <script> var h=100; var s=0; for(var i=0;i<10;i++){ h=h/2; s+=h; } s=s*2+100; </script> 累积:将一系列的数据乘积到一
-
详解JavaScript调用栈、尾递归和手动优化
调用栈(Call Stack) 调用栈(Call Stack)是一个基本的计算机概念,这里引入一个概念:栈帧. 栈帧是指为一个函数调用单独分配的那部分栈空间. 当运行的程序从当前函数调用另外一个函数时,就会为下一个函数建立一个新的栈帧,并且进入这个栈帧,这个栈帧称为当前帧.而原来的函数也有一个对应的栈帧,被称为调用帧.每一个栈帧里面都会存入当前函数的局部变量. 当函数被调用时,就会被加入到调用栈顶部,执行结束之后,就会从调用栈顶部移除该函数.并将程序运行权利(帧指针)交给此时栈顶的栈帧.这种后进
-
JS尾递归的实现方法及代码优化技巧
本文实例讲述了JS尾递归的实现方法及代码优化技巧.分享给大家供大家参考,具体如下: 在学习数据结构和算法的时候,我们都知道所有的递归都是可以优化成栈+循环的. 对于特定的递归函数,一般我们都是手动对它们进行优化的. 在学习scala的时候,接触到尾递归的概念.我们只要将递归写成尾递归方式,编译器会自动帮助我们优化. ps:并不是所有的递归都可以改写成尾递归 在js中,尾递归通常会被解释器优化.然而,并不是所有的js解释器都支持尾递归优化. 对于不支持尾递归优化的环境,我们需要手动将递归优化成栈+
-
详解js中Array的方法及技巧
JS Array的一些方法在实际中很常用,这里整理记录下来,一是为了常常回顾,二也是方便大家 Map map():返回一个新的Array,每个元素为调用function的结果 语法: array.map(function(currentValue,index,arr), thisValue) 举例: var numbers = [65, 44, 12, 4], changedValue; function multiplyArrayElement(num) { return num * 2; }
-
jQuery插件artDialog.js使用与关闭方法示例
本文实例讲述了jQuery插件artDialog.js使用与关闭方法.分享给大家供大家参考,具体如下: 子窗口关闭artdialog终极解决方案: window.parent.window.art.dialog({ id: 'qin123' }).close(); <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-t
-
JS弹性运动实现方法分析
本文实例分析了JS弹性运动实现方法.分享给大家供大家参考,具体如下: 描述:像弹簧一样左右弹动,最后缓慢停下来 一.加减速运动 1.加速运动 var iSpeed=0; iSpeed++; 速度越来越快,最后冲出去 2.减速运动 var iSpeed=20; iSpeed--; 速度越来越慢,降到0后开始变负值往反方向运动 二.弹性运动 1.在目标点左边,加速:目标点右边,减速,如 if(div1.offsetLeft<300){ iSpeed=iSpeed+1; //等同iSpeed++; }
-
JS实现Ajax的方法分析
本文实例分析了JS实现Ajax的方法.分享给大家供大家参考,具体如下: 一.什么是Ajax 不刷新的情况下读取数据或提交数据 (最早出现ajax:谷歌地图,拖动一下出现一片新的视野) 应用:用户注册.在线聊天.微博 特性:只能从服务器上去读取数据(所以我们需要配置自己的服务器程序AMP) 二.使用Ajax 1.基础:请求并显示静态TXT文件 btn.onclick=function(){ ajax('abc.txt',function(str){ alert(str); }); } ①Ajax里
-
thinkPHP js文件中U方法不被解析问题的解决方法
本文实例分析了thinkPHP js文件中U方法不被解析问题.分享给大家供大家参考,具体如下: 我想在js文件中写ajax, 写完发现异常, 本以为是js文件中不支持ajax 后来发现时地址解析错误. 也就是U方法在js文件中不被解析. 貌似thinkphp解析,tpl文件中的一些元素. js文件中的ajax function ajaxCheckTel(tel,id){ var res = ''; $.ajax({ type:"post", url:ajaxurl, // 地址解析有误
-
JS获取日期的方法实例【昨天,今天,明天,前n天,后n天的日期】
本文实例讲述了JS获取日期的方法.分享给大家供大家参考,具体如下: 原理很简单,一天的时间的毫秒数是1000*60*60*24, 前n天的日期就是现在日期换成毫秒-n*1000*60*60*24. 再把这个值换成日期即可(通过setTime方法) <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> &l
-
JS访问DOM节点方法详解
本文实例讲述了JS访问DOM节点方法.分享给大家供大家参考,具体如下: 查找并访问节点 你可通过若干种方法来查找您希望操作的元素: 通过使用 getElementById() 和 getElementsByTagName() 方法 通过使用一个元素节点的 parentNode.firstChild 以及 lastChild 属性 getElementById() 和 getElementsByTagName() getElementById() 和 getElementsByTagName()
-
JS碰撞运动实现方法详解
本文实例分析了JS碰撞运动实现方法.分享给大家供大家参考,具体如下: 描述:撞到目标点弹回来(速度反转) 一.无重力的漂浮div var div1=document.getElementById("div1"); var iSpeedX=6; var iSpeedY=8; setInterval(function(){ var l=div1.offsetLeft+iSpeedX; var t=div1.offsetTop+iSpeedY; if(t>=document.docum
-
JS表单验证方法实例小结【电话、身份证号、Email、中文、特殊字符、身份证号等】
本文实例总结了JS表单验证方法.分享给大家供大家参考,具体如下: 回回写表单,回回要写不同的检查JS,很麻烦,后来写了通用的检查函数,很粗糙,但比较实用,以后再好好改改: 包含页: Check-Form.js 代码如下: //规则检查排序 function RegCheck(objs) { var str = objs.checktype; switch (str) { case "cn" : //要检查的表单控件的输入类型必须为中文 return CnWordRegCheck(obj
随机推荐
- spring四种依赖注入方式的详细介绍
- Java读取Properties文件的七种方法的总结
- 微信公众平台天气预报功能开发
- IIS7.5下301重定向的设置方法(及伪静态后301重定向出错案例)
- 修改编辑注册表的方法实现修改盘符
- 用VBScript实现压缩目录中的所有文件(Zip)
- 使用批处理删除HOSTS中特定内容的行的代码
- Android中RecyclerView拖拽、侧删功能的实现代码
- python调用Moxa PCOMM Lite通过串口Ymodem协议实现发送文件
- PHP 抓取网页图片并且另存为的实现代码
- ip138中各种客户端验证js代码
- js实现可输入可选择的select下拉框
- html下利用javascript连数据库
- 基于jquery实现轮播特效
- jsonp跨域请求详解
- javascript表单验证大全
- Nginx服务器上搭建图片缓存服务的基本配置解析
- 100多行PHP代码实现socks5代理服务器[2]
- C语言变量类型与输出控制用法实例教程
- Android AutoCompleteTextView自动提示文本框实例代码