尾调用

Posted on In

尾调用

Tail Call 是函数式编程的一个重要概念，就是指某个函数的最后一步是调用另一个函数。

1
2
3
function f(x) {
  return g(x)
}

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

1
2
3
4
function f(x) {
  if (x > 0) return t(x)
  return m(x)
}

尾调用优化

函数调用会在内存中形成一个 call frame，保存调用位置和内部变量等信息。所有的 call frame 形成一个 call stack。
尾调用由于是函数的最后一步操作，所以不需要保留外层函数的 call frame，这就叫 Tail Call Optimization，即只保留内层函数的调用帧。

尾递归

递归非常耗内存，因为需要同时保存多个 call frame，很容易发生 stack overflow。但对于尾递归来说，由于只存在一个 call frame，所以不会发生溢出。

1
2
3
4
5
6
7
function Fibonacci(n) {
  if (n <= 1) return 1
  return Fibonacci(n - 1) + Fibonacci(n - 2)
}
console.log(Fibonacci(10)) //89
console.log(Fibonacci(100)) //overflow
console.log(Fibonacci(500)) //overflow

尾递归优化如下：

1
2
3
4
5
6
7
function Fibonacci(n, ac1 = 1, ac2 = 1) {
  if (n <= 1) return ac2
  return Fibonacci(n - 1, ac2, ac1 + ac2)
}
console.log(Fibonacci(10)) //89
console.log(Fibonacci(100)) //573147844013817200000
console.log(Fibonacci(500)) //2.2559151616193602e+104

由此可见，尾调用优化对递归操作意义重大，所有 ECMAScript 的实现都必须部署尾调用优化。

递归函数的改写

函数式编程有一个概念，叫 currying，将多参数的函数转换成单参数的形式。

1
2
3
4
5
6
7
8
9
10
11
12
//阶乘的例子
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) //fn, n 都已设定
factorial(5) //传 m 120

第二种方法就是使用 ES6 的默认函数值

1
2
3
4
function factorial(n, total = 1) {
  if (n === 1) return total
  return factorial(n - 1, n * total)
}

尾递归优化的实现

将递归转换成循环执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function sum(x, y) {
  //累加函数
  if (y > 0) return sum(x + 1, y - 1)
  else return x
}
// sum(1, 100000); //RangeError: Maximum call stack size exceeded
//用 trampoline 将递归转换为循环执行
function trampoline(f) {
  while (f && f instanceof Function) {
    f = f()
  }
  return f
}
function sum1(x, y) {
  if (y > 0) return sum1.bind(null, x + 1, y - 1)
  else return x
}
trampoline(sum1(1, 100000)) //100001

使用状态变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function tco(f) {
  var value
  var active = false
  var accumulated = []
  return function accumulator() {
    accumulated.push(arguments)
    if (!active) {
      active = true
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift())
      }
      active = false
      return value
    }
  }
}
var sum = tco(function (x, y) {
  if (y > 0) return sum(x + 1, y - 1)
  else return x
})