尾调用和尾递归

尾调用

• 指某个函数的最后一步是调用另一个函数
• 函数调用会在内存形成一个"调用记录"，又称"调用帧"（call frame），保存调用位置和内部变量等信息
• 所有的调用记录，就形成一个"调用栈"（call stack）
• 尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了
• 应用：优化递归

尾递归

• 函数调用自身，称为递归。如果尾调用自身，就称为尾递归
• 递归耗费内存，因为需要保存多个调用记录，容易发生栈溢出错误
• 但对于尾递归，只存在一个调用记录，所以不会发生栈溢出

改写方法

• 把所有用到的内部变量改写成函数的参数
• 可以使用柯里化，将多参数的函数转换成单参数的形式

// 没有尾递归 复杂度 O(n)
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5);

// 改写为尾递归 复杂度 O(1)
function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1);

// 柯里化
function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5);

// 使用 es6 默认参数
function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5);