账号密码登录
微信安全登录
微信扫描二维码登录

登录后绑定QQ、微信即可实现信息互通

手机验证码登录
找回密码返回
邮箱找回 手机找回
注册账号返回
其他登录方式
分享
  • 收藏
    X
    关于尾调用优化的疑问
    35
    0

    首先这个TCO尾调用优化在ES6中的严格模式下才有作用,但是对于这个函数优化有些疑问

    什么是尾调用优化

    尾调用之所以与其他调用不同,就在于它的特殊的调用位置。
    我们知道,函数调用会在内存形成一个"调用记录",又称"调用帧"(call frame),保存调用位置和内部变量等信息。如果在函数A的内部调用函数B,那么在A的调用记录上方,还会形成一个B的调用记录。等到B运行结束,将结果返回到A,B的调用记录才会消失。如果函数B内部还调用函数C,那就还有一个C的调用记录栈,以此类推。所有的调用记录,就形成一个"调用栈"(call stack)。
    尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用记录,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用记录,取代外层函数的调用记录就可以了。

    疑问1 来源于链接描述

    代码1 未进行尾调用优化

    function factorial(n) {
      if (n === 1) return 1;
      return n * factorial(n - 1);
    }
    
    factorial(5) // 120

    代码2 进行了尾调用优化

    function factorial(n, total) {
      if (n === 1) return total;
      return factorial(n - 1, n * total);
    }
    
    factorial(5, 1) // 120

    真心是没看出来哪里进行了优化,一个参数的传递哪里体现出了tco,在我看来factorial函数还是在不断地调用自身,形成一个循环调用帧(因为每次自调用都会用到上一次外层函数的参数,所以会形成一个很庞大的调用帧纪录),但是这个例子中实在是没看出来哪里进行了优化

    疑问2 来源于链接描述

    代码1

    //使用递归将求和过程复杂化
    function sum(x, y) {
        if (y > 0) {
          return sum(x + 1, y - 1);
        } else {
          return x;
        }
    }
    
    sum(1, 10); // => 11

    代码2

    function sum(x, y) {
        function recur(a, b) {
            if (b > 0) {
                return recur(a + 1, b - 1);
            } else {
                return a;
            }
        }
    //尾递归即在程序尾部调用自身,注意这里没有其他的运算
        return recur(x, y);
    }
    
    sum(1, 10); // => 11

    代码2 在recur函数的外层包裹了一个函数,实现了大框架上面recur这个尾调用不依赖sum这个外层函数的参数,所以实现了recur是sum的尾调用(recur不依赖sum,不会存储sum这个函数的调用纪录),但是sum的内层函数recur不还是和代码1 一样么,还是在继续递归,又形成了很庞大的调用帧纪录,所以不明白这样给递归函数包裹了一层外层函数有什么意义?或者说这种写法原理是什么?内层函数还是该递归递归
    按我的理解解决递归的性能就该类似动态规划一般:把每次的执行结果保存在一个变量中,而每次循环只是将结果重新赋值给这个变量继续提供给下一次循环,这样不就可以避免存储上一次的调用帧,防止内存溢出
    例入:只是一个优化方面,不用仔细带入上面两个疑问
    代码1

    function fib(n){
        if(n < 2){
            return n;
        }else{
            return fib(n - 1) + fib(n - 2);
        }
    }
    console.log(fib(10));   // 55

    代码2

    function fibDyn(n){
        var prev = 1;
        var middle = 1;
        var result = 1;
    
        for(var i = 2; i < n; i++){
            result = prev + middle;
            prev = middle;
            middle = result;
        }
        return result;
    }
    fibDyn(10)  // 55
    0
    打赏
    收藏
    点击回答
    您的回答被采纳后将获得:提问者悬赏的 11 元积分
        全部回答
    • 0
    更多回答
    扫一扫访问手机版
    • 回到顶部
    • 回到顶部