写出正确的尾递归代码
你可能早已耳闻，在 erlang 中，循环变成了递归。
你很可能常常看见这样的代码，并因为它是来自于 erlang 官方的文档 getting start with erlang 而觉得这样的代码，可能就是传说中的尾递归。
- -module(tut1).
- -export([fac/1]).
- fac(1) ->
- 1;
- fac(N) ->
- N * fac(N - 1).
没错，一个函数自己调用自己，这就是递归。但，这真的就是传说中可以通过编译优化得“和循环一样快，没有额外开销”的尾递归么？递归和尾递归，是否存在差异呢？
我们可以做一个试验。
为了速度考虑，我们稍微修改我们要递归的函数，从 f(x)=x*f(x-1) 变成 f(x)=x+f(x-1) (这叫啥数列来着，我忘了)。这么改是为了让我们不用等到胡子白就能看到效果。写成代码就是这样子的：
- -module(t1).
- -export([fac/1]).
- fac(1) ->
- 1;
- fac(N) ->
- N + fac(N - 1).
我们来 run 一下：
- Eshell V5.4.13 (abort with ^G)
- 1> c(t1).
- {ok,t1}
- 2> memory(total).
- 4368086
- 3> t1:fac(100000000).
- Crash dump was written to: erl_crash.dump
- eheap_alloc: Cannot allocate 1140328500 bytes of memory (of type "heap").
- abnormal program termination
呵呵，我的机器差，才到 100M 就挂了，如果你的机器好，尽管在后面多加几个 0 好了。
问题是，不是说尾递归相当于循环么？怎么会告诉我不能从堆中分配内存呢？
莫非 erlang 的尾递归，只存在于传说之中？
其实，这个问题的实质是，这的确是递归，但不是尾递归。试问又哪有递归又不狂费内存的东西呢？所以……
那，尾递归又是怎样的呢？我们来看看上面这个方法的另一个版本。
- -module(t2).
- -export([fac/1]).
- fac(N) ->
- fac_i(N, 1).
- fac_i(1, X) ->
- X;
- fac_i(N, X) ->
- fac_i(N - 1, N + X).
再来 run 一下：
- Eshell V5.4.13 (abort with ^G)
- 1> c(t2).
- {ok,t2}
- 2> t2:fac(100000000).
- 5000000050000000
呵呵，莫名奇妙吧。
Joe Armstrong 爷爷告诉我们：
The important thing to note about tail-recursive functions is that they can run in loops without consuming stack space. Such function are oden called “iterative functions.”
在上面第一个实现(t1)中：
- ...
- fac(N) ->
- N + fac(N - 1).
- ...
在 fac(N) 计算时，需要把 N 先保存在 stack 里面，以便 fac(N -1) 算完了可以相加，得到结果然并返回。
如果循环次数少，这当然没事，不就是暂存一个数字嘛。咱内存多，不嫌弃。
可是，如果你的代码是准备运行很多次，比如说就像上面的1亿次或者更多时，这个开销就大了，于是当然就 Over 没商量了。
第二个实现(t2)中：
- ...
- fac_i(1, X) ->
- X;
- fac_i(N, X) ->
- fac_i(N - 1, N + X).
- ...
没啥需要缓存，所以，编译器帮你优化成循环了。
嘿嘿。就这么点诀窍。
Comments
其实尾递归也就是一个线性迭代过程，递归计算过程和递归过程是不一样的，尾递归只是个递归过程，而不是一个递归计算过程，他的计算过程是迭代的，基本上非函数式的语言，他们对任何递归过程的解释所消耗的内存总与过程调用的数目成正比，即使计算过程是迭代的，所以这些语言就衍生出for,while 等等“循环结构”。
@simohayha，你说的有道理，关于为什么需要在 erlang 中用尾递归来实现循环，我是这么理解的。
其他语言之中的循环，如 for/while 的都依赖于一个共享的变量，通过更改和检查这个共享变量的值，实现循环的流程控制。而 erlang 的一个原则是 share nothing，变量只能一次 bind ，而且设置之后不能改变。在这个前提下，上述循环的实现方式就不再可行。
函数的参数和运算结果，属于中间值，他的使用并不违背这一原则，实际上，函数的递归也是一种循环，只不过，如果不优化递归对于资源的占用，就没有实际应用的价值。
如果能解决资源消耗问题，那么递归对于 erlang 这样 share nothing 的语言，就是一个实现循环的绝好方法。所幸，要满足这样的优化条件，并不复杂，只需要保证函数本身的“可迭代性”就成。这一般可以通过增加表示迭代结果的参数来完成。比如：
优化后变成：
可以留意到，函数的对外接口并没有改变，仍然是 fac/1 。但在它的实现函数上。主要的改变是：引入了一个 X 参数，这里 X 的值是上一次迭代的运算结果，而 N 已经变成了循环的控制变量(每次迭代 N 减1)，而 fac_i(1, X) 仍是这个尾递归的终结器。
增加一个参数，就把递归变成尾递归。其实还是挺简单的。
其实你所说的那些erlang的特性，也就是 函数式语言的特性了，我用scheme也写了个尾递归，这个就非常清晰了，尾递归也就是多引入了几个参数。
[code]
(define (f a b n)
(if (= n 1)
a
(f (+ a b) (+ b 1) (- n 1))))
(define (g n)
(f 1 2 n))
(g 3)
[/code]
@simohayha scheme 俺不懂的说。
说实话，我觉得尾递归在语法表达上让人糊涂，不好理解，完全不如 for/while 之类的语法来得简单明了。
窃以为 erlang 强调尾递归实属无奈，因为在语法层面（变量绑定一次不可更改）它并没有实现循环其他简便易行的方式。一个语言如果连循环都写得费劲，又有何用？好在尾递归解此厄困，善哉善哉。就是比较难懂一点。
是不是尾递归一个简单的判断方法就是看它的函数返回涉及不涉及额外运算，涉及的就不是尾递归，因为需要保留状态到stack里面。
递归一般用在不确定循环次数的场合，确定的就用list comprehension，比for好啊。不确定次数的循环传统上用while true里面再跳转也让人糊涂，对吧？
其实递归和尾递归并不是很复杂的概念，很多人觉得不好理解在我看来也许是眼睛抬得有点高了，只看到高级的数学概念，当然不是说这样不好，玩 FP 嘛自然就是在玩数学，只是有时向另外的方向看一看，也许会有想不到的收获，现在不妨让我们从低级的东东入手，来看一看递归和尾递归。
下面我们用 forth 来写几个不同版本的阶乘函数，forth 不是函数型语言，也不完全是通常所说的命令式语言，而是一个很低级（也许比 c 还低级）、很接近汇编的“古怪”语言，但写出来的代码却惊人的短小，执行效率也非常高，但既不能说它是编译型也不能说是解释型，总之是个很有趣的东东，我发现在学习别的语言（像 FP ）遇到困难时，对照 forth 的概念，难题往往迎刃而解，不胡扯了，回到正题:
或者
这两个 word （也就是函数）是一样的，但第一个容易理解，而第二个非常之小，编译后只有 22 bytes ，请注意括号中的是注释，说明堆栈在 word 执行前后的变化情况，现在调用它来计算 5 和 6 的阶乘:
细节就不在这说了，总之你执行这个的时候，随着递归次数的增加，你的堆栈会最终变成 （ 5 4 3 2 1 1 ），然后顺序做乘法，最后得到结果 120 ，看到了吧，堆栈会随着递归的次数不断的增长，如果你用它来计算一个很大的数，结果必然是堆栈溢出， GAME OVER 了，下面来看尾递归:
代码写得有点难看，“dup 1-” 连着用了两次，不管了，大家将就着看吧！如果有高手看到这难看的 code ，还请多多包涵、多多指点，下面调用它来计算 5 的阶乘:
程序运行之前堆栈是（ 1 5 ），执行了一次后变成了（ 20 3 ），这是什么啊？呵呵，5 × 4 × 1 ＝ 20 ，这个结果放到了原来 1 的位置上，下一个要计算的数 3 放到了原来 5 的位置上，也就是栈顶，接着再一次递归调用，3 × 2 × 20 ＝ 120 ，下一个要计算的数是 1 ，堆栈变成了（ 120 1 ），最后，由于 1 < 2 ，执行 drop 丢掉 1 ，然后停止递归，堆栈中留下了结果 120 。
现在明白了吧，所谓尾递归，就是说递归函数要在每次程序的最后调用自己，同时每次递归都要与上一次的运算结果共同作用产生一个新结果（第一次要多输入一个用于保存中间结果的参数，在这个例子中就是 1 。），然后把这个结果放回堆栈中，并等待下一次的调用，这样的话，堆栈并没有增长也就不存在溢出的问题了。而通常的递归是每次递归产生的结果是不完全并独立的，并不立即与上一次的结果进行运算，而是一个个的保存在堆栈中，导致堆栈不断的增长，到最后递归结束时，再来做所有剩下的运算。楼上所说的“是不是尾递归一个简单的判断方法就是看它的函数返回涉及不涉及额外运算”，我觉得并不完全，尾递归可以涉及额外的运算，只要你保证下次递归开始时，堆栈还是原来的样子就行了。
好了，但还有一个问题，就是现在每次调用尾递归程序时，要多输入一个参数 1 ，是有点难看啊！呵呵，这个好办，象上面的 Erlang 版累加函数一样，封装一下 word “尾递归阶乘”吧:
测试一下:
如果你看懂了上面的 forth 代码，相信你一定会觉得不过如此，并且可以结合前面的 Erlang 代码来看，也就明白了 Erlang 的尾递归到底在做什么！
为方便参考，这里也给出一个循环的版本:
运行:
注意，这里堆栈也并没有增长，但却使用了一个循环变量: i 。
楼上说的很对，尾递归是基于堆栈不额外增加的前提，不额外增加堆栈并不表示不能改变堆栈上数据的值，尾递归一般需要在堆栈上额外增加一个用于记录操作函数返回结果的变量，然后对这个变量和每次递归函数的返回结果迭代运算，最后将此变量作为最终结果返回
呵呵，咬文嚼字一下，既然在堆栈上那就不是传统意义上的“变量”了，在这里用“变量”这个词，也许会让人感到迷惑。
Write a Comment