首页 > 代码库 > 尾递归

尾递归

参考:http://www.ruanyifeng.com/blog/2015/04/tail-call.html

 

什么是尾递归呢?

函数最后一步是调用自身,就称为尾递归。

尾递归可以用循环实现。

 

什么是尾调用:

某个函数的最后一步是调用另一个函数。

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

上面代码中,函数f的最后一步是调用函数g,这就叫尾调用。

以下两种情况,都不属于尾调用。


// 情况一
function f(x){
  let y = g(x);
  return y;
}

// 情况二
function f(x){
  return g(x) + 1;
}

上面代码中,情况一是调用函数g之后,还有别的操作,所以不属于尾调用,即使语义完全一样。情况二也属于调用后还有操作,即使写在一行内。

尾调用不一定出现在函数尾部,只要是最后一步操作即可。


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

上面代码中,函数m和n都属于尾调用,因为它们都是函数f的最后一步操作。

什么是尾递归呢?

函数调用自身,称为递归。如果尾调用自身,就称为尾递归。

递归非常耗费内存,因为需要同时保存成千上百个调用记录,很容易发生"栈溢出"错误(stack overflow)。但对于尾递归来说,由于只存在一个调用记录,所以永远不会发生"栈溢出"错误。


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

factorial(5) // 120

上面代码是一个阶乘函数,计算n的阶乘,最多需要保存n个调用记录,复杂度 O(n) 。

如果改写成尾递归,只保留一个调用记录,复杂度 O(1) 。


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

factorial(5, 1) // 120

尾递归