ES6尾递归优化的实现

落日映苍穹つ 2022-06-08 11:30 145阅读 0赞

先看一个正常的递归函数。

function sum(x, y) { 
      if (y > 0) {
        return sum(x + 1, y - 1);
      } else {
        return x;
      }
    }
    
    sum(1, 100000)
    // Uncaught RangeError: Maximum call stack size exceeded(…)

上面代码中，sum是一个递归函数，参数x是需要累加的值，参数y控制递归次数。一旦指定sum递归100000次，就会报错，提示超出调用栈的最大次数。

可以将递归执行转为循环执行。

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
      }
    });
    
    sum(1, 100000)
    // 100001

上面代码中，tco函数是尾递归优化的实现，它的奥妙就在于状态变量active。默认情况下，这个变量是不激活的。一旦进入尾递归优化的过程，这个变量就激活了。然后，每一轮递归sum返回的都是undefined，所以就避免了递归执行；而accumulated数组存放每一轮sum执行的参数，总是有值的，这就保证了accumulator函数内部的while循环总是会执行。这样就很巧妙地将“递归”改成了“循环”，而后一轮的参数会取代前一轮的参数，保证了调用栈只有一层。

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关 java 递归尾递归_java8使用lambda实现Java的尾递归

原标题：java8使用lambda实现Java的尾递归前言本篇介绍的不是什么新知识，而是对前面讲解的一些知识的综合运用。众所周知，递归是解决复杂问题的一个很有效的方式，

╰+哭是因爲堅強的太久メ/ 2022年11月05日 11:55/ 0 赞/ 283 阅读

相关尾递归

尾递归如果要说尾递归的话，那么首先应该先说一下递归函数。递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但是循环的逻辑不如递归清晰易理解

刺骨的言语ヽ痛彻心扉/ 2022年08月20日 04:13/ 0 赞/ 211 阅读

相关 ES6尾递归优化的实现

先看一个正常的递归函数。 function sum(x, y) { if (y > 0) { return sum(x + 1, y -

落日映苍穹つ/ 2022年06月08日 11:30/ 0 赞/ 146 阅读

相关浅谈尾递归的优化

在[ 浅谈尾调用和尾递归 ][Link 1]这篇博文中，我谈了什么是尾递归以及编译器如何优化尾递归。这篇文章，咱来个具体的例子，通过汇编代码来看看优化和不优化的区别。求阶

港控/mmm°/ 2022年06月01日 03:40/ 0 赞/ 235 阅读

相关 Kotlin尾递归优化

一、尾递归优化 1.递归的一种特殊形式 2.调用自身后无其他的操作 3.tailrec关键字提示编译器尾递归优化二、具体的来看看一下代码说明 pack

墨蓝/ 2022年05月28日 09:16/ 0 赞/ 180 阅读

相关尾递归

什么是尾递归什么是尾递归呢?(tail recursion), 顾名思议，就是一种“不一样的”递归，说到它的不一样，就得先说说一般的递归。对于一般的递归，比如下面

逃离我推掉我的手/ 2022年05月18日 09:21/ 0 赞/ 221 阅读

相关尾递归

尾递归就是说一个递归函数，在return语句中调用了这个递归函数本身，如图所示。从理论上来说，尾递归都可以用非递归的方法实现。 ![这里写图片描述][70] [70]

秒速五厘米/ 2022年05月15日 02:27/ 0 赞/ 215 阅读

相关 09 尾递归优化

尾递归，顾名思义，就是递归中调用自身的部分在函数体的最后一句。我们知道，递归调用对于栈大小的考验是非常大的，也经常会因为这个导致 StackOverflow，所以尾递归优化也是

古城微笑少年丶/ 2022年04月25日 07:18/ 0 赞/ 208 阅读

相关尾递归

1、递归简单的来说递归就是一个函数直接或间接地调用自身，是为直接或间接递归。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满

傷城~/ 2022年02月16日 15:29/ 0 赞/ 259 阅读

相关【转】递归与优化：尾递归

了解尾递归之前，先了解一下尾调用。 > 在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位

落日映苍穹つ/ 2021年12月05日 22:05/ 0 赞/ 293 阅读