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

发表于

一、尾调用

尾调用（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运行结束，将结果返回到A，B的调用帧才会消失。

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

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

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：返回调用当前函数的那个函数。

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