Erlang 没有 for 或者 each 之类的循环迭代结构, 循环迭代靠的是递归(Recursion).

比如, 计算 0 到 N 的累加和, 循环迭代可以这么写:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def sum(n)
  total = 0
  while n != 0
    total += n
    n -= 1
  end
  return total
end

# [*(0..n)].inject(&:+)

Erlang 用递归这么写:

1
2


sum(0) -> 0;
sum(N) -> sum(N-1) + N.

像 Ruby, JavaScript 等语言, 其实也可以用递归方式做同样的事情, 但是由于实现层面的限制和低效, 递归的作用难以得到发挥, 所以从效率上考虑, 还是用循环迭代才是正道.

上面的递归写法看起来没啥大问题, 但是, 当数字 N 非常大的时候, 就会发现, 占用的内存会膨胀起来.

比如, 在我自己的机器上试了一下, 计算零到一亿的和,

内存使用最高时候飙到了 7 个 G.

因为, 在 sum 中, sum(N-1) 调用完成以后, 在返回之前还有事情没做完, 那就是加 N, 一直都没做完就得一直保持着内存.

所以, Erlang 还能好好的用递归来替代循环来玩耍吗? 答案肯定是可以的. 那么, 也就要用到接下来说的尾递归了.

尾递归

先把用尾递归改写结果奉上:

1
2
3
4


tail_sum(N) -> tail_sum(N, 0).

tail_sum(0, Total) -> Total;
tail_sum(N, Total) -> tail_sum(N-1, Total + N

尾递归是尾调用的一个特例, 那么什么又是尾调用呢? 简单的说, 函数在调用完成以后就没事可做了(除了返回), 那么就是尾调用.

比如这里, 上面说了, 在 sum 中, sum(N-1) 调用完成以后还要加上 N, 所以, sum 不能算作尾调用, 而后面的, tail_sum, 在 tail_sum(N-1, Total+N) 调用完成了以后就可以拍拍屁股完事了, 而调用的返回值也就是整个函数的返回值了.

另一方面, Erlang 采用了尾调用优化(last call optimization),

当编译器识别出尾调用(函数返回前的最后一个任务)时, 会生成一段特殊代码, 这段代码会在执行尾调用之前从栈中扔掉当前调用的所有信息. 此时, 当前调用基本无事可做, 只需告知被调用的函数后续即将发生一次尾调用: “嘿! 完事儿的时候直接把结果告诉我的调用者就好了, 我收工了哦.” 因此, 尾调用不会导致栈的膨胀.

在 tail_sum 中, Total 扮演的是累加器参数的角色, 用于在单个变量中完成信息累加(而不是将信息记在栈上回头再取). 编写尾递归函数时, 往往至少需要一个这样的额外参数, 有时候可能会是多个. 这个变量必须在循环启动的时候初始化, 因此这里需要两个函数(Erlang 不支持参数默认值). 一个用作前端接口, 一个用作主循环. 最终, 用于保存循环过程中的临时信息的参数将被丢弃, 其他参数则成为最终返回值的一部分.

再多一个例子演示尾递归, 来自 Learn You Some Erlang for great good! 的题目,

编写一个列表拼合函数（zipping function）. 这个函数以两个长度相同的列表为参数, 把它们合并成一个元组列表, 每个元组中有两个数据项.

普通版本的递归很容易实现:

1
2


zip([], []) -> [];
zip([H1|T1], [H2|T2]) -> [{H1,H2}|zip(T1, T2)].

同上面说的一样, 当参数是两个数不尽的列表时候, 这个写法会很容易就耗尽内存, 因为最后的调用在执行完函数以后还要和先前得到的元组组合成新的列表, 再没到最后一次调用之前, 栈中都要保存着已生成的元组.

要写尾递归, 我的做法比较简单粗暴,

首先是观察基本情况, 就是输入的参数最简单的时候会是什么样的呢? 毫无疑问, 上面的例子最简单的情况就是两个空列表, tail_zip([], []) -> []., 次简单的时候是长度为 1 的列表, tail_zip([X],[Y]) -> [{X, Y}].
基本观察到这, 写出前端的接收函数 tail_zip(L1,L2) -> tail_zip(L1,L2, []).
写出得出结果的函数子句 tail_zip([], [], L) -> L;
接着是主函数的定义 tail_zip([H1|T1], [H2|T2], L)
因为是尾递归, 所以, 主函数的函数体都是尾调用的形式, 对应着上面的得出结果的函数子句, 基本就可以写出 tail_zip(T1, T2, [{H1,H2}|L])

1
2
3
4


tail_zip(L1, L2) -> reverse(tail_zip(L1, L2, [])).

tail_zip([], [], L) -> L;
tail_zip([H1|T1], [H2|T2], L) -> tail_zip(T1, T2, [{H1,H2}|L]).

最后, 由于是尾递归, 如果不做一次 reverse 的话得到的其实是 [{c,3},{b,2},{a,1}]

虽然多了一次 reverse, 但是, 内存上还是节省的, 对于短列表来说, 可能会发现普通递归版本的运行速度要快于尾递归版本, 但是随着列表规模增大, 反转列表占据的时间比重会越来越小.

好吧, 写完出来好像很轻松的样子, 其实理解这也花了不少时间的, 刚开始觉得超级烧脑的, 甚至直接跳过了这一部分的内容了.

Erlang and OTP in Action 里边有教如何编写递归函数的窍门.

在 Ruby 上测试了一下, 不管是普通的递归还是尾递归的写法, 加到某个数就耗尽内存报错 SystemStackError: stack level too deep. 比如我当时的执行环境, 大概是累加到 10000 多一点就歇菜不能加下去了.

JavaScript 貌似也是类似, 不过据说 ECMAScript 2015 的严格模式支持尾调用优化, 有待测试