【IT168 技术文档】你可能早已耳闻，在 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) (这叫啥数列来着，我忘了)。这么改是为了让我们不用等到胡子白就能看到效果。写成代码就是这样子的：

　　下载: t1.erl

　　-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 的尾递归，只存在于传说之中?

　　其实，这个问题的实质是，这的确是递归，但不是尾递归。试问又哪有递归又不狂费内存的东西呢?所以……

　　那，尾递归又是怎样的呢?我们来看看上面这个方法的另一个版本。

　　下载: t2.erl

　　-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).
　　...

　　没啥需要缓存，所以，编译器帮你优化成循环了。

　　嘿嘿。就这么点诀窍。