遞歸函數掛起，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

它並不終止，因爲您在每種情況下都會創建一個新的非空列表：即使該列表僅包含一個空列表作爲其唯一成員，它總是非空列表（[[]]是非空列表一名成員的名單）。

正確的列表如下終止：[ Something | [] ]。

考慮到這一點

所以......

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

在大多數函數式語言「適當的名單」是利弊式列表。查看the Wikipedia entry on "cons"和the Erlang documentation about lists，然後冥想一下您在示例代碼中看到的列表操作示例。

注意

1. 把空白的運營商是件好事;它會阻止你使用箭頭和二進制語法操作符相互緊挨着做混淆的事情，同時避免其他一些含糊之處（而且它更容易閱讀）。

2. 正如史蒂夫指出，你注意到了內存爆炸是因爲，雖然你的函數是遞歸的，它不是尾遞歸 - 也就是說，要做1 + list_length(Xs)葉待審批工作，必須留在參考疊加。要有任何要添加1的內容，必須完成list_length/1的執行，返回一個值，在這種情況下，請記住待處理值的次數與列表中的成員次數一樣多。請閱讀Steve的答案，以獲取如何使用累加器值寫入尾遞歸函數的示例。

Answer 2

由於OP是學習二郎，還要注意的是，list_length/1功能，因爲它的加法運算，這就需要運行遞歸調用函數，取它的返回值，加1，不服從tail call optimization它，並返回結果。這需要堆棧空間，這意味着如果列表足夠長，則可以用完堆棧。

考慮使用此方法來代替：

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

這種方法，這是在二郎代碼很常見的，在list_length/1創建一個累加器保持長度值，它初始化爲0，並把它傳遞給list_length/2，它不遞歸。 list_length/2的每次調用都會累加累加器，當列表爲空時，list_length/2的第一個子句返回累加器作爲結果。但是請注意，這裏的加法操作發生在之前發生遞歸調用，這意味着調用是真正的tail調用，因此不需要額外的堆棧空間。

對於非初學者的Erlang編程人員來說，可以使用erlc -S編譯該模塊的原始版本和修改版本，並檢查生成的Erlang彙編程序。對於原始版本，彙編程序包含調用堆棧空間的allocate，並使用call進行遞歸調用，其中call是正常函數調用的指令。但是對於這個修改版本，沒有生成allocate調用，而是使用call調用call_only進行遞歸，該調用爲tail調用進行了優化。