当前位置: 萬仟网 > IT编程>开发语言>JavaScript > ES6 入门系列 (三) 尾递归

ES6 入门系列 (三) 尾递归

2019年06月12日 07:22  | 萬仟网IT编程  | 我要评论

  递归我们不陌生,

  那什么是尾递归呢?

  为什么要用尾递归呢?

  尾递归怎么用呢?

  带着这三个问题我们来了解它,

我们知道递归非常耗费内存,一不小心就会发生‘栈溢出’, 相信你一定遇到过这个错误: stack overflow,

尾递归就是用来优化递归的这个问题的。

  尾递归的定义: 在函数的最后一步返回自身,也就是显示地return自身就称为尾递归。对于尾递归来说,

由于只存在一个调用帧,所以永远不会发生‘栈溢出’。

  我们来举例说明尾递归的好处:

  • 比如计算n的阶乘, 我们首先想到找规律, n的阶乘等于n* (n-1)的阶乘
  • 找出口1的阶乘等于1
  • 然后我们就很自然的用递归写出
  • function jiecheng(n) {
        if (n===1) {
            return 1
        }
        return n * jiecheng(n -1);
    }
    const result = jiecheng(5);
    
    console.log(result);  // 120

    很自然, so easy有木有,

   but,  这样我们每递归一次,上一次的调用记录还保存着, 也就是说我们计算n的阶乘最多要保存n个调用记录,复杂度为o(n).

   改成尾递归:

   

function weijiecheng(n, total=1) {
    if (n === 1) {
        return total;
    }
    return weijiecheng(n-1, n * total);
}

console.log(weijiecheng(5), 'wei'); // 120

  把中间变量改写成函数的参数, 这样就只保存了一个调用记录,复杂度为o(1)。

  再用蹦床函数对尾递归进行优化,把递归执行转换成循环执行:

function trampoline(f) {
    while(f && f instanceof function) {
         f = f ();
    }      
}
trampoline(weijiecheng(5, 1))

 

如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复

相关文章:

◎已有 0 人评论

Copyright © 2019  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com