函数扩展-尾调用和尾递归

一、尾调用

尾调用(Tail Call)函数式编程的一个重要概念,本身非常简单,一句话就能说清楚,就是指某个函数的最后一步是调用另一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 函数f的最后一步是调用函数g,这就叫尾调用
function f(x) {
return g(x);
}

// 尾调用不一定出现在函数尾部,只要是最后一步操作即可
function f(x) {
if (x > 0) {
return m(x)
}
return n(x);
}

// 以下三种情况,都不属于尾调用
// 情况一
function f(x) {
let y = g(x);
return y;
}

// 情况二
function f(x) {
return g(x) + 1;
}

// 情况三
function f(x) {
g(x);
}


二、尾调用优化

函数调用会在内存形成一个调用帧(call frame)保存调用位置和内部变量等信息。所有的调用帧,就形成一个调用栈(call stack)

  • 如果在函数A的内部调用函数B,那么在A的调用帧上方,还会形成一个B的调用帧。等到B运行结束,将结果返回到AB的调用帧才会消失。

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

注意:只有不再用到外层函数的内部变量,内层函数的调用帧才会取代外层函数的调用帧,否则就无法进行尾调用优化

1
2
3
4
5
6
7
8
9
// 不会进行尾调用优化,因为内层函数inner用到了外层函数addOne的内部变量one
function addOne(a) {
var one = 1;

function inner(b) {
return b + one;
}
return inner(a);
}


三、尾递归

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 计算n的阶乘,最多需要保存n个调用记录,复杂度 O(n) 
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}

factorial(5) // 120

// 改写成尾递归,只保留一个调用记录,复杂度 O(1)
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}

factorial(5, 1) // 120
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 非尾递归的 Fibonacci 数列
function Fibonacci (n) {
if ( n <= 1 ) {return 1};

return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89
Fibonacci(100) // 堆栈溢出
Fibonacci(500) // 堆栈溢出


// 尾递归优化过的 Fibonacci 数列
// 只要函数参数使用了默认值、解构赋值、或者扩展运算符,
// 那么函数内部就不能显式设定为严格模式,否则会报错
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};

return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity

注:ES6 的尾调用优化只在严格模式下开启,正常模式是无效的。(验证:结论错误,Fibonacci2是正常模式

这是因为在正常模式下,函数内部有两个变量,可以跟踪函数的调用栈。

  • func.arguments:返回调用时函数的参数。
  • func.caller:返回调用当前函数的那个函数。

尾调用优化发生时,函数的调用栈会改写,因此上面两个变量就会失真。严格模式禁用这两个变量,所以尾调用模式仅在严格模式下生效。