文享日志

函数的尾调用优化

JavaScript

发表于2017年12月24日22:45:18

0条评论 205次阅读

        尾调用(Tail Call)是函数式编程的一个重要概念,是指某个函数的最后一步是调用另一个函数。
        函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。
        如果在函数A的内部调用函数B,那么在A的调用帧上方,还会形成一个B的调用帧。等到B运行结束,将结果返回到A,B的调用帧才会消失。如果函数B内部还调用函数C,那就还有一个C的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。
function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

// 等同于
function f() {
  return g(3);
}
f();

// 等同于
g(3);

上面代码中,如果函数g不是尾调用,函数f就需要保存内部变量m和n的值、g的调用位置等信息。但由于调用g之后,函数f就结束了,所以执行到最后一步,完全可以删除f(x)的调用帧,只保留g(3)的调用帧。

这就叫做“尾调用优化”(Tail call optimization),即只保留内层函数的调用帧。如果所有函数都是尾调用,那么完全可以做到每次执行时,调用帧只有一项,这将大大节省内存。这就是“尾调用优化”的意义。


注意:尾调用尾调用优化发生时,函数的调用栈会改写,因此caller,argument这两个变量就会失真。严格模式禁用这两个变量,所以尾调用模式仅在严格模式下生效


函数尾递归指的是尾调用自身。

尾递归只保留一个调用帧,所以永远不会发生溢出等错误。但这种只能在严格模式下使用,正常模式下也可以实现尾递归调用优化。

参考代码如下:

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


👍 0  👎 0
共有0条评论

发表新评论

提交

广告展示

腾讯云推广 阿里云推广