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程序设计有所帮助。

赞 (0)

相关推荐

  • 详解JavaScript调用栈、尾递归和手动优化

    详解JavaScript调用栈、尾递归和手动优化

    调用栈(Call Stack) 调用栈(Call Stack)是一个基本的计算机概念,这里引入一个概念:栈帧. 栈帧是指为一个函数调用单独分配的那部分栈空间. 当运行的程序从当前函数调用另外一个函数时,就会为下一个函数建立一个新的栈帧,并且进入这个栈帧,这个栈帧称为当前帧.而原来的函数也有一个对应的栈帧,被称为调用帧.每一个栈帧里面都会存入当前函数的局部变量. 当函数被调用时,就会被加入到调用栈顶部,执行结束之后,就会从调用栈顶部移除该函数.并将程序运行权利(帧指针)交给此时栈顶的栈帧.这种后进

  • 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递归函数解“汉诺塔”算法代码解析

    "汉诺塔"是一个著名的益智游戏.塔上有3根柱子和一套直径各不相同的空心圆盘.开始时柱子上的所有圆盘都按照从小到大的顺序堆叠.目标是通过每次移动一个圆盘到另一根柱子,最终把一堆圆盘移动到目标柱子上,过程中不允许把交大的圆盘放置在较小的圆盘之上. 仔细解读这段话,如果有10个圆盘甚至更多,那操作步骤绝对多到让人震惊,但目标是把一堆圆盘移动到目标柱子上,如果把上面的9个圆盘看成一套,第10个圆盘看成另一套,先移动9个圆盘到另一根柱子上,再把上面8个圆盘看成一套,第9个圆盘看成另一套--依次类

  • JavaScript递归算法生成树形菜单

    JavaScript递归算法生成树形菜单

    本文实例为大家分享了js生成树形菜单的具体代码,供大家参考,具体内容如下 1.最终效果图(这里仅为实现算法,并加载至页面,不做任何css界面优化) 注释:本示例包含三级目录菜单,但实际上可支持N级(可使用该代码自行测试) 2.数据源 菜单信息一般来源于数据库中数据表,且为自连接表,其中包含主要字段(主键,菜单名称,父级id): 本示例在前端页面中使用对象数组模拟从数据库获取菜单信息: var menuArry = [ { id: 1, name: "办公管理", pid: 0 }, {

  • 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累加、迭代、穷举、递归等常用算法实例小结

    本文实例讲述了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> 累积:将一系列的数据乘积到一

  • 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获取日期的方法实例【昨天,今天,明天,前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

随机推荐