《JavaScript函数式编程思想》——递归

第7章  递归

王二、张三和赵四一日无聊，决定玩击鼓传花讲冷笑话的游戏。王二和张三围成一圈传花，赵四负责击鼓。张三接连讲了几个诸如小菜、狐狸狡猾的笑话。花停在了王二的手中。
王二：这个笑话很短。你要保证听完后不生气我就说。
张三：你说吧。
王二：张三。
张三：怎么了？
王二：笑话说完了，就两个字。
张三欲发怒。
王二：欸，你刚才说好了不会生气的。
张三只好作罢。新一轮开始，花又停在王二的手中。
王二：张三不是个笑话。
张三再次欲发怒。
王二：别生气，我说的是冷笑话，就表示不好笑啊。
花又一次停在王二的手中。
王二：[张三不是个笑话]不是个笑话。
第四次花停在王二的手中。
王二：[[[张三不是个笑话]不是个笑话]不是个笑话]。
……

7.1  调用自身
7.1.1  递归的思路
7.1.2  带累积参数的递归函数
7.2  递归的数据结构
7.2.1  构建列表
7.2.2  树
7.3  递归与迭代
7.3.1  名称
7.3.2  理念和对比
7.3.3  迭代协议
7.3.4  递归协议
7.3.5  搜索树
7.4  尾部递归
7.4.1  调用堆栈
7.4.2  尾部调用优化
7.4.3  怎样算是尾部调用
7.4.4  尾部递归

7.5  递归的效率

我们来计算经典的斐波那契数列。菲波那契数列的通项公式为，当n=0和1时，A(n)=n；当n>=2时，A(n)=A(n-1)+A(n-2)。如果让一个数学不错又刚学习编程的高中生来写计算斐波那契项的函数，结果可能会是这样。

function fibonacci1(n) {
    const phi = (1 + Math.sqrt(5)) / 2;
    if (n < 2) {
        return n;
    }
    return (Math.pow(phi, n) + Math.pow(1 - phi, n)) / (phi * (3 - phi));
}
f.log(fibonacci1(10))
//=> 55.007272246494842705

他的思路如下：将等式A(n)=A(n-1)+A(n-2)变形为A(n)+x*A(n-1)=(1+x)*[A(n-1)+1/(1+x)*A(n-2)]。令x=1/(1+x)，可得1元2次方程x^2+x-1=0，解出x=[-1+sqrt(5)]/2或[-1-sqrt(5)]/2。因为A(n)+x*A(n-1)构成一个等比数列，再加上初始两项的值，可求得A(n)+x*A(n-1)的值。再利用这个公式递归地消去A(n-1)，计算出通项A(n)的值。

这样的解法会让数学老师高兴，计算机老师难过。计算机被当成计算器来用。另外，由于运算中涉及到小数，计算结果与本应是整数的精确值相比有微小的误差，如上面的fibonacci1(10)精确值是55。

正常的计算方法可以采用迭代。

function fibonacci2(n) {
    if (n < 2) {
        return n;
    }
    let a = 0, b = 1, c;
    for (let i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
f.log(fibonacci2(10))
//=> 55

也可以采用递归。

function fibonacci3(n) {
    if (n < 2) {
        return n;
    }
    return fibonacci3(n - 1) + fibonacci3(n - 2);
}
f.log(fibonacci3(10))
//=> 55

三个版本中，采用递归的版本最简短，它只是将斐波那契数列的数学定义用编程语言写出来。到现在为止，三个函数表现都还基本不错。但当我们求更大的斐波那契项时，情况开始有变化了。

f.log(fibonacci1(100))
//=> 354224848179261800000
f.log(fibonacci2(100))
//=> 354224848179261800000
f.log(fibonacci3(100))
//=> 一觉醒来还是没有结果

 fibonacci1和fibonacci2都很快得出了一致的结果（因为数字太大，fibonacci1返回值中的小数被忽略了），而fibonacci3则永远都得不出结果。出了什么问题呢？

考察fibonacci3的计算过程，可以让我们找出原因。本章所有此前出现的递归函数有一个共同点，返回语句只包含一次递归调用，用数列的语言来说就是，当前项的值只依赖于前一项。而fibonacci3的递归算法在求第n项A(n)时，不仅要利用前一项A(n-1)，还要依赖更前一项A(n-2)，这导致对此前项的大量重复计算，项数越小，重复的次数越多。令B(i)为第i项被计算的次数，则有

B(i) = 1;  i = n, n - 1

B(i) = B(i + 1) + B(i + 2);  i < n - 1

这样，B(i)形成了一个有趣的逆的斐波那契数列。求A(n)时有：

B(i) = A(n + 1 - i)

换一个角度来看，令C(i)为求A(i)时需要做的加法的次数，则有

C(i) = 0;  i = 0, 1

C(i) = 1 + C(i - 1) + C(i - 2);  i > 1

令D(i) = C(i) + 1，有

D(i) = 1;  i = 0, 1

D(i) = D(i - 1) + D(i - 2)

所以D(i)又形成一个斐波那契数列。并可因此得出：

C(n) = A(n + 1) - 1

A(n)是以几何级数增长，所以fibonacci3在n较大时所做的重复计算量会变得十分惊人。与它相对应的采用迭代的程序fibonacci2，有

B(n) = 1;  n为任意值

C(n) = 0;  n = 0, 1

C(n) = n - 1;  n > 1

因而当n增长时，一直能保持很快的速度。

聪明的读者也许已经想到了解决的方法，本书之前介绍的“记忆化”模式的功用正是避免以同样的参数多次调用函数时的重复计算。记忆化普通函数很简单，只需将其传递给memoize函数，返回的就是记忆化的版本。这种方法对递归函数却不适用，因为递归函数体内有对自身的调用，无法利用记忆化的版本，要想记住对某个参数的计算结果，只有用memoize函数类似的写法，修改递归函数。

const fibonacci4 = function () {
    const memory = new Map();
    return function fibonacci4(n) {
        if (m.has(n, memory)) {
            return m.get(n, memory);
        }
        if (n < 2) {
            m.set(n, n, memory);
        } else {
            m.set(n, fibonacci4(n - 1) + fibonacci4(n - 2), memory);
        }
        return m.get(n, memory);
    }
}();

因为这里的参数限定为非负整数，所以用于记忆计算结果的Map，可以换成数组，这样函数可以改写得更简洁，运行速度也更快。 

const fibonacci5 = function () {
    const memory = [0, 1];
    return function fibonacci5(n) {
        if (memory.length <= n) {
            memory[n] = fibonacci5(n - 1) + fibonacci5(n - 2);
        }
        return memory[n];
    }
}();

在这两个版本的递归算法中，虽然形式上在计算第n项时，仍然包含两次递归调用，但实际上对于每个n，函数都只计算了一次，其他对第n项的引用，都是从记忆中读取的，所以求第n项过程中进行的加法运算次数与迭代算法相同，具有同样的可伸缩性。

仔细的读者会发现，迄今为止的三个递归版本，都不算是尾部调用。所以当n很大时，还是会出现调用堆栈耗尽的问题。

fibonacci5(10**8)
//=> Maximum call stack size exceeded

 上一节已经介绍了，可以利用累积参数将函数转换成尾部递归。在返回语句只包含一次递归调用的情况下，转换的方法是一目了然的。而对fibonacci3这样返回语句包含两次递归调用的函数，以前的方法就无效了。思路的突破口是，一次递归调用需要一个参数来累积，多次递归调用时，每次调用都需要一个参数来累积。这样就得到fibonacci3尾部递归的版本。

function fibonacci6(n) {
    return _fibonacci(n, 0, 1);

    function _fibonacci(n, a, b) {
        if (n === 0) {
            return a;
        }
        return _fibonacci(n - 1, b, a + b);
    }
}

最后，我们来比试一下各种版本算法的速度。

export function doUnto(...args) {
    return function (fn) {
        return fn(...args);
    }
}

const cTookTime = f.unary(f.curry(f.tookTime, 2));
let fns = f.map(cTookTime, [fibonacci1, fibonacci2, fibonacci4, fibonacci4,
        fibonacci5, fibonacci5, fibonacci6]);
fibonacci5,fibonacci6]);
f.forEach(f.doUnto(1000), fns);
//=> 4.346655768693734e+208
//=> fibonacci1(1000): 1.828857421875ms
//=> 4.346655768693743e+208
//=> fibonacci2(1000): 0.243896484375ms
//=> 4.346655768693743e+208
//=> fibonacci4(1000): 3.918212890625ms
//=> 4.346655768693743e+208
//=> fibonacci4(1000): 0.126953125ms
//=> 4.346655768693743e+208
//=> fibonacci5(1000): 0.372802734375ms
//=> 4.346655768693743e+208
//=> fibonacci5(1000): 0.156005859375ms
//=> 4.346655768693743e+208
//=> fibonacci6(1000): 0.223876953125ms

多次测试，每个函数花费的时间会有波动，但总体上的排名没有多少出入。从这个结果能读出很多有趣的信息。fibonacci1直接根据斐波那契数列项的公式来计算，因为涉及开方和小数的乘方等运算，并不算快。fibonacci2的迭代算法，名列前茅。fibonacci3没有参赛资格。fibonacci4用映射数据结构作缓存，第一次计算时速度最慢，再次计算时读取缓存，速度最快。fibonacci5用数组作缓存，第一次计算时，速度已经和不需缓存的最快算法在一个数量级上；第二次计算时，依靠读取缓存，速度和fibonacci4差不多。fibonacci6的尾部递归算法，与迭代算法不相上下。

7.6  小结

更多内容，请参看拙著：

《JavaScript函数式编程思想》（京东）

《JavaScript函数式编程思想》（当当）

《JavaScript函数式编程思想》（亚马逊）

《JavaScript函数式编程思想》（天猫）