尾递归

介绍

在 ES 6 之前，就算我们递归函数写的没问题，也会因为浏览器对调用栈大小的限制，出现栈溢出（ stack overflow）的问题。后来在 ES 6 的规范中就增加了一项内存优化机制，让 JS 引擎在满足条件的时候可以重用栈帧。也叫做「尾调用优化」。如果这项技术使用到递归函数里，就是我们常提的「尾递归优化」。

那栈帧是什么呢？它属于调用栈，对应着一个未运行完的函数。同时，栈帧中保存了该函数的返回地址和局部变量。重用栈帧意味着两个函数先后用到了相同的那个栈帧。那重用栈帧有什么好处呢？它不仅让函数的运行速度更快了，还让内存更节省了

优化

尾递归是指在一个方法内部，递归调用后直接return，没有任何多余的指令了

常见的一个例子是: 斐波那契数列

常规写法：

function fib(n) {
  if (n === 1) {
    return 1;
  } else if (n === 0) {
    return 0;
  }

  return fib(n - 1) + fib(n - 2);
}

console.time("start");
const f = fib(40); //1.4s
console.log("f", f);
console.timeEnd("start");

循环版本

function fib(n) {
  let a = 0; //  相当于 memo[i]
  let b = 1; // 相当于 memo[i+1]
  let sum = 0;
  let i = 0;

  while (i < n) {
    sum = a + b;
    a = b;
    b = sum;
    i++;
  }

  return a;
}

console.time("start");
const f = fib(40); //8~10ms
console.log("f", f);
console.timeEnd("start");

尾递归版本

function fib(n) {
  return fibInner(0, 1, n);
}

//思路：递归改为循环思路
function fibInner(a, b, n) {
  if (n === 0) {
    return a;
  }

  return fibInner(b, a + b, n - 1);
}

console.time("start");
const f = fib(40);  //8~10ms
console.log("f", f);
console.timeEnd("start");

参考

1. 关于取消 ES6 函数尾递归的相关探究 (opens new window)