尾递归与递归

什么是递归

递归是什么就不多说了，下面举个例子

function f(n) {
  if (n === 1) {
    return 1
  }
  return n * f(n - 1)
}
f(3) // 6

递归非常耗费内存，因为递归调用栈中需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误。

什么是尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。----百度百科

简单说，函数在末尾调用函数，就称为尾递归。

//尾递归
function f(x) {
  return g(x);
}

function f(x) {
  if (x > 0) {
    return m(x)
  }
  return n(x);
}

//以下两种都不是尾递归
function f(x) {
  let y = g(x);
  return y;
}

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

尾递归是函数最后一步调用，在所有递归调用记录形成的调用栈中，不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用递归调用中最后一次函数调用的记录就可以了。

递归函数改写尾递归函数

同样是这个求取阶乘的函数，递归函数与尾递归函数写法如下

//递归
//需要保存n条调用记录，复杂度为O(n)
function f(n) {
  if (n === 1) {
    return 1
  }
  return n * f(n - 1)
}
f(3) // 6

//尾递归
//只需调用最后一次调用记录，复杂度O(1)
function f(n, total) {
  if (n === 1) {
    return total
  }
  return f(n - 1, n * total)
}
f(3, 1) // 6

 参考文章

尾调用优化