【填坑】尾递归优化其实很简单

brambles 发布于 2016年04月04日 | 更新于 6月前
无人欣赏。

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

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

共3条回复
tinyfool 回复于 2016年04月04日

你咋开始研究静态分析了?

因为王垠说PL没前途,所以你去搞PL了么?

brambles 回复于 2016年04月04日

1楼 @tinyfool 没有啊,只是随便折腾了一下而已。

brambles 回复于 6月前

1楼 @tinyfool

我这篇文章最后的坑已经填上了,两年了才想起来填上

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

登录 或者 注册