递归

递归，就是函数调用自身。 条件：

• 递归终止条件。防止无限递归下去，导致内存溢出，程序出错。
• 递归条件。让函数继续递归的条件。

尾递归

尾递归，即在函数尾位置调用自身（或是一个尾调用本身的其他函数等等）。尾递归也是递归的一种特殊情形。

尾递归在普通尾调用的基础上，多了2个特征：

• 在尾部调用的是函数自身
• 可通过优化，使得计算仅占常量空间

实现阶乘，普通递归形式：

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

计算n的阶乘，都要计算n-1的阶乘，空间复杂度是 O(n)

尾递归形式如下：

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

factorial(5) // 120

每次返回一个新函数，不需要存储上一个函数，尾递归只需要保存一个调用栈，复杂度是 O(1)

应用

求和

斐波那契数列

数组扁平化