8

アルゴリズムの本を読んだところ、アッカーマン関数を末尾再帰にすることはできません（彼らが言うのは「反復に変換できない」ということです）。私はこれについてかなり困惑しているので、これを試してみました：

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＃コードです）。

私の問題は、これが実際に末尾再帰であるかどうかわからないということです。確認してもらえますか？そうでない場合、なぜですか？そして最終的に、アッカーマン関数は原始再帰ではないと人々が言うとき、それはどういう意味ですか？

ありがとう！

4

2 に答える 2

15

はい、末尾再帰です。すべての関数は、継続渡しスタイルへの明示的な変換によってテールレックにすることができます。

これは、関数が一定のメモリで実行されることを意味するものではありません。割り当てが必要な継続のスタックを構築します。継続を非機能化して、そのデータを単純な代数的データ型として表す方が効率的かもしれません。

原始再帰であることは、数学理論で使用される特定の形式の再帰的定義の表現力に関連する非常に異なる概念ですが、ご存知のように、おそらくコンピュータサイエンスにはあまり関係がありません。現在のすべてのプログラミング言語などの関数構成（ゲーデルのシステムTから開始）は、はるかに強力です。

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

于 2010-12-12T23:25:58.993 に答える
2

はい。

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

末尾再帰関数は、引数のサイズが制限されている場合にのみ、このような反復に変えることができます。あなたの例（そして継続を使用するほとんどすべての再帰関数）では、contパラメーターはあらゆる手段と目的のために、任意のサイズに成長できるスタックです。実際、継続渡しスタイルの全体的なポイントは、代わりに、コールスタックに通常存在するデータ（「戻った後に何をするか」）を継続パラメーターに格納することです。

于 2010-12-13T14:54:11.653 に答える