悠哉悠哉

一.尾调用

指函数在结束时返回并调用另一个函数

条件：

尾函数不需要是最后一行，但必须是最后一步操作
不能有多余的计算操作

实例：

// yes
function f(x){
  if (x > 0) {
    // 不需要是函数体最后一行，最终执行就行
    return m(x)
  }
  return g(x);
}
 
// no: 结尾并不是函数执行
function f(x){
  let y = g(x);
  return y;
}
// no: 多余的计算操作
function f(x){
  return g(x) + 1;
}
// no：没有返回，并不属于尾部
function f(x){
  g(x);
}

二.尾调用优化

闭包利用了变量常驻的特点，让返回函数能持久使用主函数的内容；而利用此特点，尾函数体内不使用外部变量，促使只保留尾函数自身的执行栈，让主函数中的栈自己销毁，则会形成尾调用优化。此优化方法仅存在于严格模式下的Safari浏览器（严格模式是因为正常情况下函数体内的arguments与caller会跟踪执行内容，导致失真，而严格模式下两者是无法使用的）

条件：

尾函数体内不使用外部变量，促使只保留尾函数自身的执行栈，让主函数中的栈自己销毁
严格模式
Safari

实例：

// yes 虽然有m+n操作，但在执行g方法后f方法就可以结束了
function f() {
  let m = 1;
  let n = 2;
  return g(m + n); 
}
f();
 
// yes 等同于
function f() {
  return g(3);
}
f();
 
// yes 等同于
g(3);
 
// no: 尾函数用到了主函数的one变量
function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

三.尾递归

递归函数的递归执行位置在最后，贯彻尾函数的定义。正常的递归性能开销较大，且会导致栈溢出，而尾递归不会发生栈溢出

条件：

尾函数的定义
尾函数是自身

实例：

// 普通递归
function Fibonacci (n) {
  if ( n <= 1 ) {return 1};
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 栈溢出 超时
Fibonacci(500) // 栈溢出 超时

// 尾递归
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};
  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

四.尾递归优化

正常情况下尾递归只能在严格模式下执行，而尾递归优化就是为了处理环境问题；其原理就是用循环巧妙的代替递归

// 尾递归
function sum(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1);
  } else {
    return x;
  }
}
sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)

// 尾递归优化
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
 
/**
 * 解析（此函数行为较为抽象）
 * 先使用tco实现sum函数
 * 第一次执行sum时，将默认参数存入accumulated，且将尾递归的关键变量active被修改为true，
 * 至此之后，sum执行将因为active而总是返回undefined（此时递归就消失了），与此同时，while循环时每执行一次sum就将旧的参数从accumulated丢弃、将新参数存入accumulated
 * 这样一存一删，让sum的执行与accumulated的参数存入互相扶持，直到不再执行新的sum
 */

尾调用优化

一.尾调用 #

二.尾调用优化 #

三.尾递归 #

四.尾递归优化 #

一.尾调用

二.尾调用优化

三.尾递归

四.尾递归优化