この実装はテール再帰的ですか

Question

アルゴリズムの本では、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＃コードです）。

私の問題は、実際にはこれが末尾再帰であるかどうかはわかりません。それが確認できますか？そうでない場合、なぜですか？そして、最終的に、Ackermann関数が原始的な再帰的関数ではないと人々が言うとき、それはどういう意味ですか？

ありがとうございます！

Answer 1

はい、末尾再帰型です。 Continuation Passing Styleへの明示的な変換によって、すべての関数をtail-recにすることができます。

これは、関数が定数メモリで実行されるということではありません。割り当てが必要な連続のスタックを構築します。そのデータを単純な代数データ型として表現することの継続は、より効率的であるかもしれません（defunctionalize）。

primitive recursiveは数学理論で使用されている特定の形式の再帰的定義の表現性に関係していますが、あなたが知っているほどコンピュータ科学にはあまり関係がないかもしれません。現在のすべてのプログラミング言語などの機能構成（GödelのSystem Tで始まる）を持つシステムは、はるかに強力です。

コンピュータ言語の意味では、プリミティブ再帰関数は、すべてのループ/反復が静的に境界付けられている一般的な再帰がないプログラムに対応しています（可能な繰り返しの数はわかっています）。

Answer 2

はい。

定義上、任意の再帰関数は、束縛されていないスタック状の構造体にアクセスできる限り、反復に変換できます。興味深いのは、スタックやその他の無制限のデータストレージなしで実行できるかどうかです。

テール再帰関数は、引数のサイズが制限されている場合にのみ、そのような繰り返しに変換できます。あなたの例（および継続を使用するほぼすべての再帰関数）では、contパラメータは、すべての手段と目的のために任意のサイズに拡張可能なスタックです。確かに、継続渡しスタイルの全体のポイントは、コールスタックに通常存在するデータ（「返された後に何をするか」）を継続パラメータに格納することです。