记录一次利用CPS和蹦床技术来避免递归中的栈溢出的经历

本文记录一次利用CPS和蹦床技术来避免递归中的栈溢出的经历。

首先我们来看一段经典的递归程序：斐波那契数列

function fib(n) {
    return n <= 2
        ? 1
        : fib(n - 1) + fib(n - 2)
}
1
2
3
4
5

这个程序无法直接转为尾递归，而且最后一段fib(n - 1) + fib(n - 2)也不是尾调用（Tail Call）形式，这里控制上下文会不断增加，直至栈溢出。

首先，我们利用延续体传递风格（Continuation-passing style，简称CPS）重写该程序，将其标识为尾调用的形式，来避免控制上下文的增加：

function fib2(n) {
    return (function rec(n, f) {
        return n <= 2
            ? f(1)
            : rec(n - 1, (a) => rec(n - 2, (b) => f(a + b)))
    })(n, (a) => a)
}
1
2
3
4
5
6
7

尾调用的形式在个别语言中不会产生栈溢出（例如ChezScheme），但大部分语言还是会有栈溢出。我们利用蹦床技术改写示例：

function fib3(n) {
    let temp = (function rec(n, f) {
        return n <= 2
            ? () => f(1)
            : () => rec(n - 1, (a) => () => rec(n - 2, (b) => () => f(a + b)))
    })(n, (a) => a)

    while (typeof (temp) == 'function') {
        temp = temp()
    }
    return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12

这样改完后，在过程内部进行进一步函数调用前会先从当前函数返回，这样就避免了栈溢出。