這個實現是否是遞歸的

我在算法書中讀到Ackermann函數不能被做成尾遞歸（他們說的「它不能被轉換成迭代」）。我很困惑這個，所以我試圖想出這個：這個實現是否是遞歸的

let Ackb m n = 
    let rec rAck cont m n = 
    match (m, n) with 
     | 0, n -> cont (n+1) 
     | m, 0 -> rAck cont (m-1) 1 
     | m, n -> rAck (fun x -> rAck cont (m-1) x) m (n-1) 
    in rAck (fun x -> x) m n 
;;

（這是OCaml/F＃代碼）。

我的問題是，我不確定這實際上是尾遞歸。你能確認它是什麼嗎？如果不是，爲什麼？最終，當人們說阿克曼函數不是原始遞歸時，這意味着什麼？

謝謝！

來源

2010-12-12 Clément

當您傳遞該lambda表達式時，您仍然在構建函數調用的「堆棧」。 – 2010-12-12 22:47:22

是的，它是尾遞歸的。你可以用'-dlinear'選項用ocamlopt編譯文件。這應該可以幫助您確定您的功能是否使用尾部呼叫。 – nlucaroni 2010-12-13 16:36:11

是的，它是尾遞歸的。通過對Continuation Passing Style進行顯式轉換，可以使每個功能都可以進行尾部記錄。

這並不意味着函數將在常量內存中執行：您將構建必須分配的連續堆棧。將數據表示爲簡單代數數據類型的延續可能更有效。

正在primitive recursive是一個非常不同的概念，與數學理論中使用的某種形式的遞歸定義的表達有關，但可能與您所瞭解的計算機科學不太相關：它們的表達性非常低，和具有功能組成的系統（從哥德爾的System T開始），比如所有當前的編程語言，功能更強大。

就計算機語言而言，原始遞歸函數大致對應於沒有一般遞歸的程序，其中所有循環/迭代都是靜態有界的（可能的重複次數是已知的）。

來源

2010-12-12 23:25:58 gasche

關於原始遞歸，我認爲重要的是，原始遞歸函數可以在恆定空間中實現（假設您想計算的數量可以存儲在恆定空間中），而Ackermann函數不能。 – sepp2k 2010-12-12 23:30:22

很酷，非常感謝！ – 2010-12-14 05:47:48

是的。

根據定義，任何遞歸函數都可以轉換爲迭代，只要它可以訪問無界堆棧式構造。有趣的問題是它是否可以在沒有堆棧或任何其他無界數據存儲的情況下完成。

只有在參數大小有界的情況下，尾遞歸函數才能轉化爲這樣的迭代。在你的例子中（以及幾乎任何使用continuations的遞歸函數），cont參數適用於所有手段和目的，可以增長到任意大小。事實上，continuation-passing風格的整個方面是將通常存在於調用堆棧中的數據（「我返回後該做什麼？」）存儲在連續參數中。

來源

2010-12-13 14:54:11

這裏「按照定義」是什麼意思？你在這裏使用什麼「遞歸函數」的定義？ – 2015-11-22 12:45:20

這個實現是否是遞歸的

回答

相關問題