尾调用

... 2022-12-19 About 4 min

# 尾调用

# 尾调用优化

什么是尾调用？

尾调用（Tail Call）是函数式编程的一个重要概念，本身非常简单，就是指某个函数的最后一步式调用另一个函数

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

1
2
3

以下三种均不算是尾调用

运算之后

function f (x) {
  let y = g (x) // 在这个地方进行一些操作
  return y // 最后一步(并不一定式在函数的尾部)并不是调用另一个函数
}

1
2
3
4

调取函数并运算（这种最容易搞混淆）

function f (x) {
  return g (x) + 1 // 这种情况也不是尾调用，调用后还有操作，并不能把f的调用帧砍掉
}

1
2
3

无return

function f (x) {
  g (x)
}
// <=========>
function f (x) {
  g (x)
  return undefined
}

1
2
3
4
5
6
7
8

尾调用之所以和其他的调用不同，就在于它的特殊的调用位置

函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方还会形成一个B的调用帧，等B运行结束后，将结果返回给A，B的调用帧才会消失，（因为这个时候跟B没什么关系了），如果函数B内部调用函数C，那就还有一个C的调用帧，以此类推，所有的调用帧就形成了一个“调用栈”（call stack）

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了，因为是这样，所以可以省去至少一个调用帧，优化存在内存里面的数据

function f () {
  let a = 1
  let b = 2
  return g (a + b)
}
f()
// <==========>
function f (){
  return g (3)
}
f()
<==========> // 在这一步的时候将f的调用帧删除
g(3)

1
2
3
4
5
6
7
8
9
10
11
12
13

上面的调用就是“尾调用优化”，即只保留内层函数的调用帧，如果所有的函数都是尾调用，那么完全可以做到每次执行的时候，调用帧只有一项，这将大大节省内存，这就是“尾调用优化”的意义

所有尾调用，反正我第一时间想起来的式递归

# 尾递归

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

递归非常耗费内存，因为需要同时保存成千上万个调用帧，很容易发生“栈溢出”错误（stack overflow）。但是对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”的错误

function factorial (n) {
  if (n === 1) return 1
  return n * factorial( n - 1 ) // 这个显然不是尾调用，出了调用还有其他的操作
}

1
2
3
4

以上代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度O(n), 优化如下

function factorial (n, total = 1) {
  if (n === 1) return total
  return factorial (n-1, n * total) // 这个地方式尾调用
}

1
2
3
4

这种调用，始终只有一个调用帧，复杂度O(1)

再说一个很经典的递归函数的例子 Fibonacci 数列，也能充分说明尾递归优化的重要性

function Fibonacci (n) {
  if (n <= 1) return n
  return Fibonacci(n-1) + Fibonacci(n-2) // 显然不是尾调用
}
Fibonacci(10) // 89
Fibonacci(100) // 超时

1
2
3
4
5
6

优化：

function Fibonacci (n, total1 = 1, total2 = 1) {
  if (n <= 1) return total2
  return Fibonacci( n - 1, total2, total1 + total2 )
}
console.log(Fibonacci(10)) // 89
console.log(Fibonacci(100)) // 573147844013817200000

1
2
3
4
5
6

到目前（2018年7月3日）为止，javascript 引擎除 Safari 浏览器外，其他主流浏览器，如谷歌（包括 v8、node.js）、火狐均未实现 TCO(Tail call optimization）。由此可见，“尾调用优化”对递归操作的意义重大，没有栈溢出（或者层层递归造成的超时），相对节省内存

扩展的说点东西（尾递归的实现原理）

蹦床函数（trampoline）

let sum = (x, y) => {
  if (y) return sum(x + 1, y - 1)
  return x
}
console.log(sum(1, 100000)) // Maximum call stack size exceeded 栈溢出

1
2
3
4
5

基于上面的错误，生成一个蹦床函数

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
// 改写sum函数
let sum = (x, y) =>{
  if (y) return sum.call(null,x+1,y-1) // 这个地方会一个新的sum，已经绑定xy的函数
  return x
}
console.log(trampoline(sum(1, 100000))) // 100001 这个地方并不是可以无穷大的

1
2
3
4
5
6
7
8
9
10
11
12

尾递归的实现 (opens new window)

尾调用

# 尾调用

# 尾调用优化

# 尾递归

Description