尾调用和尾递归优化

尾调用

参考链接
TL; DR
尾调用就是指在某个函数的最后一步调用另一个函数。亦或者说把函数调用放在函数的最后。

function f(x) {
	return g(x);
}

调用栈

当在函数中调用另一个新的函数时，将会在运行栈中新建一个栈帧，并把新的函数执行所需要的变量，寄存器等放入这个栈帧。上一个函数所对应的栈帧被称为调用帧。如下图所示：
尾调用和尾递归优化
如之前所说的，尾调用就是一个函数执行的最后一步是将另一个函数调用并返回。这样就可以不用保存调用者栈帧中的参数，变量等，甚至可以不用保存调用帧，可以大大减少调用栈的大小。

尾调用优化

TL; DR
尽力做到每次调用函数时，只保留内层被调用函数的栈帧，这样可以大大节省内存。

function f() {
  let m = 1;
  let n = 2;
  return g(m + n);
}
f();

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

// 等同于
g(3);

尾递归

函数尾调用自身，就叫做尾递归
递归虽好，但是非常耗内存。如果能使用尾调用优化的思想去优化递归，那将是极好的。接下来我们看一下尾递归和非尾递归的性能差异。

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}
// 尾递归优化
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};

  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

function test1(n) {
    console.time('test'); 
    console.log(Fibonacci(n)); 
    console.timeEnd('test')
}
function test2(n) {
    console.time('test'); 
    console.log(Fibonacci2(n)); 
    console.timeEnd('test')
}

test1(10) // test: 0.873046875ms
test2(10) // test: 0.2119140625ms
test1(40) // test: 1514.0390625ms
test2(40) // test: 0.31689453125ms
test2(1000) // test: 0.67919921875ms

从上面的结果中我们可以很明显的看出尾递归优化的作用。
想要把普通递归函数改写成尾递归，就要把所有的内部变量改写成函数的参数。
为了让函数保持原来参数的形式，可以使用es6的函数默认值来初始化应该为内部变量的参数。

ES6 的尾调用优化只在严格模式下开启，正常模式是无效的。
因为正常模式下，函数内部的两个变量可以跟踪函数的调用栈。

func.arguments: 返回调用时函数的参数
func.caller: 返回调用当前函数的那个函数

尾调用优化发生时，函数的调用栈会改写，因此上面两个变量就会失真。严格模式禁用这两个变量，所以尾调用模式仅在严格模式下生效；

尾调用和尾递归优化

尾调用

调用栈

尾调用优化

尾递归

相关推荐