你正在正确地进行测试:你的函数确实不是尾递归的。为了找出原因,你可以使用 erlc -S <erlang源文件>
编译你的代码。
{function, sum_list, 2, 2}.
{label,1}.
{func_info,{atom,so},{atom,sum_list},2}.
{label,2}.
{test,is_nonempty_list,{f,3},[{x,0}]}.
{allocate,1,2}.
{get_list,{x,0},{y,0},{x,0}}.
{call,2,{f,2}}.
{gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}.
{deallocate,1}.
return.
{label,3}.
{test,is_nil,{f,1},[{x,0}]}.
{move,{x,1},{x,0}}.
return.
以下是该函数的尾递归版本的比较:
tail_sum_list([],Acc) ->
Acc;
tail_sum_list([Head|Tail],Acc) ->
tail_sum_list(Tail, Head + Acc).
编译后的结果为:
{function, tail_sum_list, 2, 5}.
{label,4}.
{func_info,{atom,so},{atom,tail_sum_list},2}.
{label,5}.
{test,is_nonempty_list,{f,6},[{x,0}]}.
{get_list,{x,0},{x,2},{x,3}}.
{gc_bif,'+',{f,0},4,[{x,2},{x,1}],{x,1}}.
{move,{x,3},{x,0}}.
{call_only,2,{f,5}}.
{label,6}.
{test,is_nil,{f,4},[{x,0}]}.
{move,{x,1},{x,0}}.
return.
相对于非递归函数中的allocate
/call
/deallocate
/return
序列,注意在尾递归版本中缺少allocate
和call_only
操作码。
Erlang "stack"很大,因此您不会遇到堆栈溢出。实际上,堆栈溢出通常意味着处理器堆栈溢出,因为处理器的堆栈指针走得太远了。传统上,进程具有有限的堆栈大小,可以通过与操作系统交互来进行调整。例如,请参见POSIX的setrlimit。
然而,Erlang执行堆栈并不是处理器堆栈,因为代码是解释执行的。每个进程都有自己的堆栈,可以通过调用操作系统内存分配函数(通常是Unix上的malloc)来扩展它。
因此,只要malloc
调用成功,您的函数就不会崩溃。
值得一提的是,实际列表L
使用的内存量与处理它的堆栈相同。实际上,列表中的每个元素都占用两个字(整数值本身,由于它们很小而被装箱为一个字,以及指向列表下一个元素的指针)。相反,堆栈在每次迭代时会通过allocate
操作码增加两个词:一个词用于由allocate
本身保存的CP
,另一个词用于当前值的请求参数(allocate
的第一个参数)。
对于64位VM的10亿个单词,列表需要至少1.5 GB的内存(实际堆栈不是每两个字就增长一次,所以需要更多内存)。在shell中监视和回收此内存非常困难,因为许多值仍然保持活动状态。如果生成一个函数,则可以查看内存使用情况:
spawn(fun() ->
io:format("~p\n", [erlang:memory()]),
L = lists:seq(1, 100000000),
io:format("~p\n", [erlang:memory()]),
sum_test:sum_list(L, 0),
io:format("~p\n", [erlang:memory()])
end).
正如您所看到的,递归调用的内存不会立即被释放。