什么是尾递归
尾递归是一种特殊的递归，相比于普通的递归(体递归），他多了一个要求:递归调用是函数执行过程的最后一步。
以计算阶乘为例，使用普通递归和尾递归的erlang代码如下:
%% 普通递归
fac(1) -> 1;
fac(N) -> N * fac(N - 1).
最后一步是计算乘法
%% 尾递归
fac(N) -> fac(N, 1).
fac(1, Acc) -> Acc;
fac(N, Acc) -> fac(N - 1, Acc * N).
最后一步是递归调用
我们知道，在不同的编程语言中，尽管内存模型不同，但函数的调用和返回都符合栈模型。当编译器看到一个函数调用的时候，会在栈空间开辟一块栈帧，当函数计算完成返回的时候将栈帧弹出，回到调用的地方继续执行。还是以计算阶乘为例，体递归调用过程如下所示:
对于尾递归，很多编程语言的编译器会做尾递归优化，从而使得递归函数可以复用当前栈帧，而不用开辟新的栈帧，从而达到节省内存和提高效率的目的，调用过程如下所示(递归出口省略):
可以看出，编译器之所以能做尾递归优化，是因为在尾递归函数中，不用暂存中间结果，当前计算的结果完全取决于下一次递归调用的结果，计算结果的累积（Accumulate）是通过传递入口参数实现的。
erlang中的递归与list
erlang是一门比较纯粹的函数式编程语言，没有其他语言中for，while之类的循环结构，循环只能够通过递归实现。正确理解递归是编写高效erlang代码的关键之一。
list是erlang中最常用的顺序存储结构，它相当于C语言中的单向链表。erlang中在list头部插入项是及其高效的，而在尾部插入项是低效的。除了单向链表本身的特性外，还是因为erlang中的变量只能够被绑定一次（变量不可变），只能通过绑定到新的变量来达到改变的效果，比如在list L0头部添加项:
L1 = [H|L0]
在尾部添加项：
L1 = L0 ++ T
在尾部添加项时，由于不能改变变量L0的值，所以必须复制L0，两种情况的示意图如下:
在erlang中，遍历list并生成新的list是非常常见的操作。先不考虑使用库函数，假如要使新list中每一项为原list中对应项的平方。为了效率，我们使用尾递归和从list头部插入项的方式。代码如下:
square(L) -> square(L, []).
square([], Acc) -> lists:reverse(Acc);
square([H|T], Acc) -> square(T, [H * H | Acc]).
注意到当到达递归终点时，我们使用BIF函数lists:reverse将Acc逆序，这是为了保证新list元素顺序与原list一致。这样的处理方式也是Learn you some Erlang for great good!中提倡的方式，因为这样可以充分利用尾递归的好处，而最后的逆序虽然也是O（N）的操作，但是是由系统提供的高效BIF函数完成的，总体来说也比使用体递归高效。但是事实真是如此吗？
erlang中尾递归一定比体递归高效吗
我们使用体递归来来完成上述平方操作，代码如下:
square2([]) -> [];
square2([H|T]) -> [H * H | square2(T)].
编写测试代码:
t() ->
L = lists:seq(1, 10000000),
{T1, V1} = timer:tc(?MODULE, square, [L]),
{T2, V2} = timer:tc(?MODULE, square2, [L]),
V1 = V2,
io:format("tail: ~p ms~n", [T1/1000]),
io:format("body: ~p ms~n", [T2/1000]),
ok.
运行结果如下所示:
可以看到对于长度10000000的list，体递归甚至稍微比尾递归快一点。改变list长度重复实验，可以看到两种方式时间效率上基本差不多，体递归稍优。这是为什么呢？
在erlang的官方文档中是这样说的:
According to the myth, using a tail-recursive function that builds a list in reverse followed by a call to lists:reverse/1 is faster than a body-recursive function that builds the list in correct order; the reason being that body-recursive functions use more memory than tail-recursive functions.
That was true to some extent before R12B. It was even more true before R7B. Today, not so much. A body-recursive function generally uses the same amount of memory as a tail-recursive function. It is generally not possible to predict whether the tail-recursive or the body-recursive version will be faster. Therefore, use the version that makes your code cleaner (hint: it is >usually the body-recursive version).
For a more thorough discussion about tail and body recursion, see Erlang’s Tail Recursion is Not a Silver Bullet.
也就是说，在较新的版本的erlang中，尾递归+reverse操作和体递归在效率上和内存使用上差距是不大的。上面的链接中有一个比较详细的比较，实际执行效率还会受到erlang中垃圾回收等操作的影响，具体哪一个比较快是难以确定的。官方给出的建议是尽量选择可读性和可维护性更好的代码编写方式（往往是体递归），除非在遍历list中顺序不重要，那么应该尽量选择尾递归。如果实在是在非常需要性能的关键代码中，根据profiling选择一个。
理解lists:foldl和lists:foldr
实际编写代码中，在能够使用库函数的地方可以不用自己编写递归函数。一是库函数的性能往往比自己实现的要好，二是可读性更高。但是使用之前，理解库函数的实现方式对于编写好的erlang代码也是相当重要的。比如遍历list时使用最多的两个函数lists:foldl好玩lists:foldr。这两个函数除了遍历方向不同外，还在于lists:foldl是使用尾递归实现的，而lists:foldr是使用体递归实现的。考虑这样一个问题，将多个string拼接成一个string。
使用lists:foldl的实现方式:
joinLL(ListOfBinary) ->
L = lists:foldl(fun(E, In) -> In ++ binary_to_list(E) end, "", ListOfBinary),
list_to_binary(L).
使用lists:foldr的实现方式:
joinLR(ListOfBinary) ->
L = lists:foldr(fun(E, In) -> binary_to_list(E) ++ In end, "", ListOfBinary),
list_to_binary(L).
拼接10000个“123”字符串的结果如下:
可以看到使用lists:foldl的效率及其低下，甚至比直接用binary进行拼接更慢，而lists:foldr的耗时就很少了。这是因为list的++操作会复制完整的左边的list，所以从左到右拼接的时间复杂度是O（N2），而且会生成很多临时的中间list，之后给垃圾回收掉。而从右到左拼接的时间复杂度为O（N）。