这篇文章的坑终于被我填上了

https://zhuanlan.zhihu.com/p/36587160

原文地址： http://lovearia.me/article/show/9

多年以前我一直觉得尾递归优化是一个多么多么高深的东西，知道后来我自己会对语言做静态分析以后，才懂得所谓的尾递归优化其实并不是什么多难的东西。接下来我就花上半个小时讲讲所谓的尾递归。

举个栗子

首先我们选择一个最简单的例子——阶乘。以下是一个用递归形式写的用来计算 n 的阶乘的函数：

``` JavaScript
const fact = (n) => {
    if (n <= 0) {
        return 1;
    } else {
        return n * fact (n - 1);
    }
};
```

我们使用递归的时候，经常会考虑一个问题，叫做”爆栈“。比如你把上面的函数放到 node 里面执行，试试 fact (10000000000000000000)，然后你就会得到一条报错信息 Maximum call stack size exceeded，这就是所谓的”爆栈“了。

函数栈的作用

栈这种数据结构怎么定义的以及怎么用大家都非常了解了，但是为什么会这么一种叫做”栈“的数据结构呢？而且当一个函数被调用的时候，我们会把函数扔进一个叫做“函数栈“的地方，但是我们为什么要用栈而不用其他的呢？

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

``` JavaScript
const main = () => {
    //...
    foo1();
    //...
    foo2();
    //...
    return;
};
```

上面是一个简单的示例代码，我们现在简单在大脑里面模拟一下这个 main 函数调用的整个过程。

1. 首先我们建立一个函数栈。这是栈 -> $
2. mian 函数调用，将 main 函数压进函数栈里面。$ main
3. 做完了一些操作以后，调用 foo1 函数，foo1 函数入栈。$ main foo1
4. foo1 函数返回并出栈。$ main
5. 做完一些操作以后，调用 foo2 函数，foo2 函数入栈。$ main foo2
6. foo2 函数返回并出栈。$ main
7. 做完余下的操作以后，main函数返回并出栈。$

上面这个过程说明了函数栈的作用是什么？就是第 4 和第 6 步的作用，让 foo1 和 foo2 函数执行完了以后能够在回到 main 函数调用 foo1 和 foo2 原来的地方。这就是栈，这种”后入先出“的数据结构的意义所在。

为什么尾递归可以优化

上面说了，函数栈的目的是啥？是保持入口环境。那么在什么情况下可以把这个入口环境给优化掉？答案不言而喻，入口环境没意义的情况下为啥要保持入口环境？尾递归，就是这种情况。

因为尾递归的情况下，我们保持这个函数的入口环境没意义，所以我们就可以把这个函数的调用栈给优化掉。比如还是那个阶乘函数把它写成尾递归的形式。

`

`` JavaScript
const fact = (n, r) => {
    if (n <= 0) {
        return 1 * r;
    } else {
        return fact (n - 1, r * n); // <= 这里的入口环境没有必要保留。
    }
};
```

所以我们就可以把他优化掉。

如何手动优化

好了，现在我们有一个尾递归函数了。假设我们的语言没有原生支持尾递归优化，那么要怎么在语言层面上手动实现一个尾递归优化呢？这其实就是一个把递归变成循环的过程嘛。

首先，把上面尾递归代码抄过来，并且套进一个 while 循环里面。因为尾递归就是在用参数来临时传递迭代的变量而已。所以我们就把尾递归的参数转换成变量，把函数体转换成循环

``` JavaScript
const fact = (n, r) => { // <= 这里把 fact 去掉， 把 n, r 作为变量提出来
    if (n <= 0) {
        return 1 * r; // <= 递归终止条件
    } else {
        return fact (n - 1, r * n); // <= 这里也把 fact 去掉，并把 (n - 1, r * n) 带入下一次迭代。
    }
};
```

得到

``` JavaScript
const fact = (x, y) => {
    let n = x;
    let r = y;
    while (true){
        if (n <= 0){
            return 1 * r; // 遇到递归终止条件就直接原封不动得 return 就好了。
        } else {
            let _r = r;
            let _n = n; // 把临时变量存下来，主要是防止后面迭代有顺序依赖的蛋疼问题。
            n = _n - 1;
            r = _r *  _n;
            continue; // 尾递归的地方就直接 continue 进入下一次迭代
        }
    };
};
```

到这里，一个尾递归函数就已经转换成了一个循环。

如何用代码自动完成

手动把尾递归转换成循环其实没什么用处（当然啦，在没有尾递归优化的语言里面可以应一下急，虽然没有尾递归优化的语言一般都有叫做”迭代器“的东东），所以我们希望能够写代码来自动优化。整个思路和过程在上一步已经解决了。

代码之后再补上 /w