尾递归与递归问题

今日看技术blog，看到一个新词汇“尾递归”，发现了递归不为人知的一面。
概括一下就是，普通的函数递归调用可能会导致性能问题，比如常见的栈溢出。

以常见的阶乘算法为例：

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

这是我经常写的、再熟悉不过的递归，然而编程中并不建议这种写法，甚至是唾弃，因为这个函数返回值是一个当前上下文中的变量与函数本身的乘积，这样的话，每次执行完此函数，上下文并没有被垃圾回收机制回收，一直常驻着，加上递归循环后风险非常大。这时尾递归显而易见成为了针对这个问题的优化手段。

先引入一个尾调用概念：

尾调用是指某个函数的最后一步是调用另一个函数，除此之外没有进行任何其他操作。

// 情况1
function f(x){
  return g(x);
}
// 情况2
function f(x){
  let y = g(x);
  return y;
}
// 情况3
function f(x){
  return g(x) + 1;
}

以上只有情况1属于尾调用，因为进行了其他操作，所以2和3都不属于尾调用。
那么尾递归的定义，相比就清楚了：尾调用自身，就称为尾递归。

优化后的阶乘写法：

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

尾递归优化，其实就是递归函数优化为尾调用形式的这个过程。

文章目录