末尾调用优化

Erlang支持末尾调用优化，从而使得函数得以在固定大小的空间内执行。存储持久数据的主要手法是将之存储于由服务器进程操纵的结构中（典型实例参见第??节）。为了令这种手法得以正常工作，服务器必须利用末尾调用优化。

如果不这么做，服务器最终将会耗尽内存空间从而无法正常工作。

尾递归

我们通过展示同一个函数的两种不同风格的写法来引入尾递归的概念，其中一种写法是尾递归的形式。考察定义如下的length函数：

length([_|T]) ->
    1 + length(T);
length([]) ->
    0.

我们不妨对legth([a,b,c])求值。length的第一个子句将问题归结为对1+length([b,c])求值。不幸的是，+运算无法立即执行，而是得延迟到length([b,c])求值完毕为止。系统必须记住这个+运算并在后续的某个阶段（此时已知length([b,c])的值）系统回溯至该执行这个+运算时再实际执行运算。

未决的运算被保存于局部数据区。这块区域的包含至少K*N个位置（其中K是一个常数，代表对length进行一次全新求值所需空间的大小，N是未决的运算数量）。

现在我们再写一个等价的求列表长度的函数，其中使用了一个累加器（参见第??节）。该函数仅占用固定大小的空间（为避免混淆，我们将之记为length1）：

length1(L) ->
    length1(L, 0).
 
length1([_|T], N) ->
    length1(T, 1 + N);
length1([], N) ->
    N.

要求length1([a,b,c])，我们首先求length1([a,b,c],0)。再归结为length1([b,c],1+0)。现在+运算可以立即执行了（因为所有参数都已知）。于是，计算length1([a,b,c])的函数求值过程为：

length1([a, b, c])
length1([a, b, c], 0)
length1([b, c], 1 + 0)
length1([b, c], 1)
length1([c], 1 + 1)
length1([c], 2)
length1([], 1 + 2)
length1([], 3)
3

尾递归函数就是在递归调用前不累计任何未决运算的函数。如果函数子句中函数体的最后一个表达式是对自身的调用或者是个常数，那么它就是尾递归子句。如果一个函数的所有子句都是尾递归子句，那么它就是一个尾递归函数。

例如：

rev(X) -> rev(X, []).
 
rev([], X) -> X;
rev([H|T], X) -> rev(T, [H|T]).

该函数就是尾递归函数，但：

append([], X) -> X;
append([H|T], X) -> [H | append(T,X)].

就不是尾递归函数，因为第二个子句的最后一个表达式（[H|append(T,X)]中的|）既不是对append的调用，也不是常数。

末尾调用优化

尾递归是更泛化的末尾调用优化（Last Call Optimisation，LCO）的一个特例。末尾调用优化可应用于任何函数子句最后一个表达式为函数调用的情况。

例如：

g(X) ->
    ...
    h(X).
 
h(X) ->
    ...
    i(X).
 
i(X) ->
 
    g(X).

上述代码定义了一组三个相互递归的函数。LCO使得对g(X)的求值可以在常数空间内完成。

仔细翻阅本书的所有服务程序示例代码会发现，这些程序都可以在常数空间[1]内执行。