尾调用、尾递归 - 《JavaScript》

尾调用
- 什么是尾调用？
- 尾调用优化
尾递归
- 什么是尾递归？
- 以阶乘函数举例 👀

💡 参考链接：阮一峰的网络日志

尾调用

什么是尾调用？

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

function f1 () {
    return f2()
}

以下两种情况都不属于尾调用，因为这两种情况在调用函数f2后还有其余操作

// 情况一
function f1 () {
    let r = f2()
    return r
} 
// 情况二
function f1 () {
    return f2() + 1
}

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

function f1(x) {
    if (x > 0) {
        return f2()  // 尾调用
    }
    return f3()      // 尾调用
}

尾调用优化

函数调用会在内存形成一个“调用记录”，也称“调用帧”，保存调用位置和内部变量等信息；

如果函数A内部调用函数B，那么在A的调用记录上方还有一个B的调用记录，等B运行结束后将结果返回到A，B的调用记录才会消失，如果B的内部还调用C，那就还有一个C的调用栈记录；
以此类推，所有的调用记录形成一个“调用栈”

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息不会再用到了，只要直接调用内层函数的调用记录，取代外层函数的调用记录就可以了😯

function f1 () {
    let a = 1
    let b = 2
    return f2(a+b)
}
f1()
// 等同于
function f1 () {
    return f2(3)
}
f1()
// 等同于
f2(3)

上面代码中，如果函数f2不是尾调用，函数f1就需要保存内部变量a、b的值，f2的调用位置等信息，正因为f2是尾调用，调用f2之后f1就结束了，此时已经可以完全删除f1()的调用记录，只保留f2(3)的调用记录；
这就叫做“尾调用优化”，即只保存内层函数的调用记录，如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存，这就是尾调用优化的意义

尾递归

什么是尾递归？

函数尾调用自身

递归非常耗费内存，因为需要保存成百上千个调用记录，容易发生“栈溢出”，对于尾递归调用来说，由于只存在一个调用记录，所以永远不会发生“栈溢出”

以阶乘函数举例 👀

没有使用尾递归时

function factorial (n) {
  if (n === 1) return 1
  return n * factorial(n-1)
}
factorial(5)        // 120

使用尾递归
```
function factorial (n, total) {
  if (n === 1) return total
return factorial(n-1, n * total)
}
factorial(5, 1)        // 120
// 可以看出这时需要传两个参数，看上去有点多余
```
- 使用正常函数调用尾递归函数 ```javascript // 尾递归函数 function tailFactorial (n, total) { if (n === 1) return total return tailFactorial(n-1, n * total) } // 阶乘函数 function factorial(n) { return tailFactorial(n, 1) }

factorial(5) // 120


   - 函数柯里化
```javascript
function currying (fn, n) {
    return function (m) {
      return fn.call(this, m, n)    
  }
}
function tailFactorial (n, total) {
    if (n === 1) return total
    return tailFactorial(n-1, n * total)
}
const factorial = currying(tailFactorial, 1)
factorial(5)     // 120

ES6函数默认值

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