Lisp中遞歸函數調用的堆棧溢出

我正在從Conrad Barski的書「Lisp的土地」學習Lisp。現在，我已經打了我的第一個攔路虎，在這裏筆者說：Lisp中遞歸函數調用的堆棧溢出

以這種方式調用自己是不是隻允許在Lisp的，但往往是顯示下面的例子功能後，大力鼓勵

算在列表中的項目：

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0))

當我調用該函數my-length含一百萬的項目清單，我得到一個堆棧溢出錯誤。所以要麼你永遠不會期望在Lisp中有很長的列表（所以也許我的用例是無用的），或者有另一種方法來計算這樣一個長列表中的項目。你能否對此有所瞭解？（順便說一句，我在Windows上使用GNU CLISP）。

來源

2013-03-07 mydoghasworms

http://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html – 2013-03-07 11:03:40

> *所以，要麼你就休想有一個長的Lisp *你知道，有一個'length'功能列表，對？這就是爲什麼你叫你'我的長度'。 – Kaz 2017-05-24 19:24:24

創建遞歸函數以在遞歸數據結構上操作確實對lisp很有用。列表（在lisp中）被定義爲遞歸數據結構，所以你應該沒問題。然而，正如你所經歷的那樣，如果使用遞歸遍歷一百萬個數據結構，那麼它也會在堆棧中分配一百萬幀，除非特別要求運行時環境分配鉅額金額，否則可能會出現堆棧溢出的堆棧空間（我不知道你是否可以在gnu clisp中做到這一點...）。首先，我認爲這表明列表數據結構並非真正適合所有事情，在這種情況下，其他結構可能會更好（但是，您可能沒有在您的lisp中找到向量） book yet ;-)

另一件事是，對於像這樣的大型遞歸是有效的，編譯器應該優化尾遞歸併將它們轉換爲迭代。我不知道clisp是否具有此功能，但您需要將您的功能更改爲實際可優化的功能。（如果「尾遞歸優化」是沒有意義的，請讓我知道，我可以挖掘出一些參考）

對於迭代的其他方式，一起來看看：

或者其他數據結構：

http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm

來源

2013-03-07 10:58:14

很酷，非常感謝。拿走我：1）列表並不是最好的，2）有其他數據結構可供查看。我很想了解更多關於尾遞歸優化的知識，但也許在稍後的階段，我已經征服了基礎知識;-)謝謝！ – mydoghasworms 2013-03-07 11:15:52

您正在尋找尾遞歸。目前你的函數定義像

(defun my-length (list) 
    (if list 
    (1+ (my-length (cdr list))) 
    0))

注意後my-length呼籲本身，它需要一個值傳遞給它的調用函數之前添加一個結果。這需要在返回之前修改該值，這意味着您需要爲每個調用分配一個新的堆棧幀，所使用的空間與列表的長度成正比。這是導致長列表上堆棧溢出的原因。

您可以重新寫它使用一個輔助功能

(defun helper (acc list) 
    (if list 
    (helper (1+ acc) (cdr list)) 
    acc)) 

(defun my-length (list) 
    (helper 0 list))

的輔助函數有兩個參數，一個積累參數acc，其中存儲列表的長度，到目前爲止，名單list這是我們計算長度的列表。

重要的一點是，helper是遞歸地寫尾，這意味着調用自己是它最後一件事。這意味着每次函數自己調用時都不需要分配一個新的堆棧框架 - 因爲最終的結果將一直通過堆棧框架的鏈路，您可以避免覆蓋舊的堆棧框架一個新的，所以你的遞歸函數可以在恆定的空間中運行。

這種形式的程序轉換 - 從遞歸（但非尾遞歸）定義到使用尾遞歸輔助函數的等價定義是函數式編程中一個重要的習慣用法 - 值得花一點時間理解。

來源

2013-03-07 11:05:11

謝謝，你已經展示了Rolf在他的回答中暗示的內容，但即使使用這個代碼（在GNU Clisp上），我仍然會遇到堆棧溢出。 – mydoghasworms 2013-03-07 11:17:11

有趣。你有沒有另一種常見的lisp實現，你可以試試它？對於是否在GNU Clisp中執行尾部呼叫優化，這個[關於通用lisp實現中尾部呼叫優化的頁面]（http://0branch.com/notes/tco-cl.html）並不清楚。 – 2013-03-07 11:29:57

我剛剛在鋼鐵銀行Common Lisp上試過，而且工作。 – mydoghasworms 2013-03-07 11:34:26

使用TCO克里斯·泰勒的例子（尾調用優化）在CLISP：

[1]> (defun helper (acc list) 
     (if list 
      (helper (1+ acc) (cdr list)) 
      acc)) 

(defun my-length (list) 
    (helper 0 list)) 

HELPER

現在編譯：

[2]> (compile 'helper) 
MY-LENGTH 
[3]> (my-length (loop repeat 100000 collect t)) 

*** - Program stack overflow. RESET

現在，上述方法無效。讓我們設置低調試級別。這允許編譯器執行TCO。

[4]> (proclaim '(optimize (debug 1))) 
NIL

再次編譯。

[5]> (compile 'helper) 
HELPER ; 
NIL ; 
NIL 
[6]> (my-length (loop repeat 100000 collect t)) 
100000 
[7]>

工程。

允許Common Lisp編譯器執行TCO通常由調試級別控制。在高調試級別下，編譯器會爲每個函數調用生成使用堆棧幀的代碼。通過這種方式，每個呼叫都可以被追蹤，並且會在回溯中看到。如果調試級別較低，編譯器可能會用編譯代碼中的跳轉替換尾調用。這些調用然後不會在回溯中看到 - 這通常會使調試更困難。

來源

2013-03-07 12:54:45

我只是想知道爲什麼這不被接受爲正確的答案。非常棒的信息，謝謝。 – Rorschach 2014-03-25 11:44:00

在此幫助下，我計算了100,000的階乘。 – Rorschach 2014-03-25 11:54:38

(DEFUN nrelem(l) 
    (if (null l) 
     0 
     (+ (nrelem (rest l)) 1) 
))

來源

2015-03-29 17:04:56 IoanCristian

Lisp中遞歸函數調用的堆棧溢出

回答

相關問題