Erlang：递归函数未进行尾递归优化导致stackoverflow？

Question

Erlang：递归函数未进行尾递归优化导致stackoverflow？

recursionerlangstack-overflowtail-call-optimization

8

有没有可能在Erlang中使用未经尾调用优化的函数来获得stackoverflow? 例如，假设我有一个这样的函数：

sum_list([],Acc) ->
   Acc;
sum_list([Head|Tail],Acc) ->
   Head + sum_list(Tail, Acc).

如果传入的列表足够大，似乎会耗尽堆栈空间并崩溃。我尝试用以下方式进行测试：

> L = lists:seq(1, 10000000).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29|...]
> sum_test:sum_list(L, 0).
50000005000000

但它从未崩溃！我用一个包含1亿个整数的列表进行了测试，它需要一段时间才能完成，但仍然从未崩溃！问题：

我是否正确地进行了测试？
如果是这样，为什么无法生成堆栈溢出？
Erlang是否正在执行某些操作以防止堆栈溢出发生？

- Stratus3D

我刚刚在检查这个问题，我认为我对于空间复杂度的理解是错误的：在所有体递归中，堆栈都会增长，但是Erlang的堆栈比你想象的要高效得多。我考虑的优化是大幅提高速度，而不是空间，使体递归与尾递归相当。请尝试使用一万亿个整数进行测试。 - zxq9

1个回答

阿里云服务器只需要99元/年，新老用户同享，点击查看详情

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- Paul Guyot · Accepted Answer

你正在正确地进行测试：你的函数确实不是尾递归的。为了找出原因，你可以使用 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).

正如您所看到的，递归调用的内存不会立即被释放。