30秒了解尾递归和尾递归优化

尾递归和尾递归优化

之前提到过尾调用，尾调用就是函数的最后一步调用另外一个函数。那么递归就是调用自身，尾递归就是再函数的最后一步调用自身。?

在计算机学里，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。---wikipedia

和尾调用一样，尾递归因为调用栈中只存在一个调用记录，因此不会像普通递归那样耗费那么多内存。

以乘阶函数为例

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

计算乘阶函数参数为 n 那么调用栈就需要保存 n 个调用记录。如果参数 n 过大直接就会导致 stack overflow

那么就需要对递归进行优化，上述代码改写：

function f(n, total = 1) { // ? total 参数保存上次调用的结果
    if (n === 1) return total
    return f(n - 1, n * total) // ⚡ total 结果和 n 相乘作为参数放入到函数中
}

默认大部分浏览器不会对尾递归进行优化

如果需要尝试可以安装 node 6.5 - 7 之间的版本测试；开启 node 需要增加 flag --harmony-tailcalls --use-strict