10.2 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的调用，也不是常数。