递归函数调用挂起，Erlang

Question

我目前正在自学 Erlang。一切都很顺利，直到我发现这个功能有问题。

-module(chapter).
-compile(export_all).

list_length([])      ->   0;
list_length([_|Xs])  ->   1+list_length([Xs]).

这是从教科书上摘下来的。当我运行此代码使用 OTP 17 时，它只是挂起，这意味着它只是如下所示。

1> c(chapter).
{ok,chapter}
2> chapter:list_length([]).
0
3> chapter:list_length([1,2]).

在任务管理器中查看时，Erlang OTP 使用了 200 Mb 到 330 Mb 的内存。这是什么原因造成的。

Answer 1

它不会终止，因为您在每种情况下都创建了一个新的非空列表：[Anything] 始终是一个非空列表，即使该列表包含一个空列表作为其唯一成员（[[]] 是一个成员的非空列表）。

一个合适的列表这样结束：[ Something | [] ].

考虑到这一点...

list_length([])      ->   0;
list_length([_|Xs])  ->   1 + list_length(Xs).

在大多数函数式语言中 "proper lists" 是 cons 风格的列表。查看 the Wikipedia entry on "cons" and the Erlang documentation about lists，然后稍微思考一下您在示例代码中看到的列表操作示例。

注释

在运算符周围放置空格是一件好事；它将防止你用彼此相邻的箭头和二进制语法运算符做混淆的事情，同时避免一些其他的歧义（而且它更容易阅读）。
正如史蒂夫指出的那样，您注意到的内存爆炸是因为虽然您的函数是递归的，但它不是 尾递归 —— 也就是说，1 + list_length(Xs) 留下待完成的工作，这必须在堆栈上留下一个引用。要让任何东西加 1，必须完成 list_length/1、return 一个值的执行，在这种情况下，请记住挂起值的次数与列表中的成员数一样多。阅读史蒂夫的回答，了解如何使用 累加器 值编写尾递归函数的示例。

Answer 2

由于 OP 正在学习 Erlang，另请注意 list_length/1 函数不适合 tail call optimization 因为它的加法运算需要运行时间来调用递归函数，取其 return 值，将其加 1，然后 return 结果。这需要栈space，也就是说如果列表足够长，可以运行出栈

改为考虑这种方法：

list_length(L)           -> list_length(L, 0).
list_length([], Acc)     -> Acc;
list_length([_|Xs], Acc) -> list_length(Xs, Acc+1).

这种方法在 Erlang 代码中很常见，它在 list_length/1 中创建一个累加器来保存长度值，将其初始化为 0 并将其传递给 list_length/2，后者执行递归。每次调用 list_length/2 然后递增累加器，当列表为空时，list_length/2 return 的第一个子句将累加器作为结果。但请注意，这里的加法运算发生在 before 递归调用发生，这意味着调用是真正的尾调用，因此不需要额外的堆栈 space.

对于非初学者的 Erlang 程序员，使用 erlc -S 编译该模块的原始版本和修改版本并检查生成的 Erlang 汇编程序可能具有指导意义。在原始版本中，汇编程序包含 allocate 调用堆栈 space 并使用 call 进行递归调用，其中 call 是正常函数调用的指令。但是对于这个修改后的版本，不会生成 allocate 调用，而是使用 call_only 执行递归，而不是使用 call，它针对尾调用进行了优化。

递归函数调用挂起，Erlang

Recursive function call hanging, Erlang

memory

windows

erlang

erlang-shell