关于尾递归、栈和迭代

[Jeffersondyj]

递归 vs 尾递归

递归

我们要先从递归讲起。首先话不多说来一个代码：

function fibonacci(n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

调用栈应该是这样：

[fibonacci(5)]
[fibonacci(4) + fibonacci(3)]
[(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))]
[((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))]
[fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)]

可以看到n=5时，调用栈长度已经是8了～
注意了，到这里为止，程序做的仅仅还只是展开而已，并没有运算真正做运算

我们普通递归的问题就在于此：展开的时候会产生非常大的中间缓存，而每一层的中间缓存都会占用我们宝贵的栈上空间
导致了当这个 n 很大的时候，栈上空间不足则会产生“爆栈”的情况

eg：把上面那段代码在浏览器里面执行：fibonacci(10000)
会报RangeError: Maximum call stack size exceeded

那有没有一种方法能够避免这样的情况呢？那当然是有的，尾递归粉墨登场～

尾递归

尾递归：
若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。
特点(维基百科尾调用词条)：
尾递归在普通尾调用的基础上，多出了2个特征：

1. 在尾部调用的是函数自身 (Self-called)；
2. 可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

我们把上面那段改成尾递归：

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

再分析一下调用栈：

fibonacci2(5)
fibonacci2(5, 0, 1)  
fibonacci2(4, 1, 1)  
fibonacci2(3, 1, 2)  
fibonacci2(2, 2, 3)  
fibonacci2(1, 3, 5)  
fibonacci2(0, 5, 8)

So，调用栈长度应该一直是1？

非也～尾递归函数依然还是递归函数，如果不优化依然跟普通递归函数一样会爆栈，该展开多少层依旧是展开多少层。不会爆栈是因为语言的编译器或者解释器所做了“尾递归优化”，才让它不会爆栈的。

你在nodejs环境执行：fibonacci2(10000)，照样报：RangeError: Maximum call stack size exceeded
ps：node v6版本在加flag的情况下，已经可以做尾递归优化了。node --harmony-tailcalls test.js
but，在node的高版本又移除了，你执行这个flag，反而会报：bad option: --harmony-tailcalls

读者：读了你文章半天，合着尾递归优化还是镜花水月，无法落地？
非也！我们可以用栈和迭代嘛～

栈和迭代

栈

栈的意义其实非常简单，五个字——保持入口环境。我们结合一段简单代码来展示一下：

function main() {
    foo();
    bar();
}

• 首先建立一个函数栈。$
• main 函数调用，将 main 函数压进函数栈里面。$ main
• 调用 foo 函数，foo函数入栈。$ main foo
• foo 函数返回并出栈。$ main
• 调用 bar 函数，bar函数入栈。$ main bar
• bar 函数返回并出栈。$ main
• main 函数返回并出栈。$

这就是栈——这种”后入先出“的数据结构的意义所在——
可以看到第 4 和第 6 步的作用，让 foo 和 bar 函数执行完了以后能够在回到 main 函数调用他们的地方
既然是保持入口环境，那么在什么情况下可以把这个入口环境给优化掉？答案不言而喻，在入口环境没意义的情况下（即尾递归）

读者：你还是纸上谈兵地讲了些原理和意义，依然没讲尾递归优化！

用迭代手动优化尾递归

function fact(n, r) { // TODO这里把 n, r 作为迭代变量提出来
    if (n <= 0) {
        return r;
    } else {
        return fact(n - 1, r * n); // TODO用迭代函数替代 fact
    }
}

=>

function fact(_n, _r) { // _n, _r 用作初始化变量
    var n = _n;
    var r = _r; // 将原来的 n, r 变量提出来，成为迭代变量
    function _fact(_n, _r) { // 迭代函数非常简单，就是更新迭代变量而已
        n = _n;
        r = _r;
    }
    _fact_loop: while (true) { // 生成一个迭代循环
        if (n <= 0) {
            return r;
        } else {
            _fact(n - 1, r * n);
            continue _fact_loop; // 执行迭代函数，并且进入下一次迭代
        }
    }
}

可以在nodejs下测试：fact(1e5, 1)，前者爆栈，后者可以返回Infinity

快速排序

function partition(arr, low, high) {
    let i = low;
    let j = high + 1;
    let k = arr[low]; // 尽量不要固定基准；如果基本有序，则随机基准；如果不确定也可以选择三数取中
    while (i < j) {
        while (arr[++i] < k && i < j);
        while (arr[--j] > k);
        if (i < j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[low] = arr[j];
    arr[j] = k;
    return j;
}

function qsort(arr, low, high) {
    if (arguments.length === 1) {
        low = 0;
        high = arr.length - 1;
    }
    if (low < high) {
        const index = partition(arr, low, high);
        qsort(arr, low, index - 1);
        qsort(arr, index + 1, high);
    }
}

function qsort1(arr, low, high) {
    if (arguments.length === 1) {
        low = 0;
        high = arr.length - 1;
    }
    while (low < high) { // TODO如果high和low比较接近时，用插入排序
        const index = partition(arr, low, high);
        qsort1(arr, low, index - 1);
        low = index + 1; // 尾递归
    }
}

在极端情况下（倒序），前者(qsort)8000爆栈，后者(qsort1)14000爆栈

拗拗概念

while转递归

while (true) {
    console.log(1);
}

=>

function do() {
    console.log(1);
    do();
}

for转递归

function forEach(arr) {
    for (var i = 0; i < arr.length ; ++i) {
        console.log(arr[i]);
    }
}

=>

function forEach(arr) {
    var i = 0; // 循环变量丢外面
    function go() {
        console.log(arr[i]);
        if (++i < arr.length) {
            go();
        }
    }
    go();
}

or

function forEach(arr, i = 0) { // 循环变量传值
    console.log(arr[i]);
    if (++i < arr.length) {
        forEach(arr, i);
    }
}

TBD：迷宫问题

0代表墙，走过的路不可重复，期望从(1,1)走到(n,m)

22202
00202
22222
20202
20233

返回布尔（是否可以到达n,m）
返回途经的值最大的路径？