アルゴリズムの本を読んだところ、アッカーマン関数を末尾再帰にすることはできません(彼らが言うのは「反復に変換できない」ということです)。私はこれについてかなり困惑しているので、これを試してみました:
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#コードです)。
私の問題は、これが実際に末尾再帰であるかどうかわからないということです。確認してもらえますか?そうでない場合、なぜですか?そして最終的に、アッカーマン関数は原始再帰ではないと人々が言うとき、それはどういう意味ですか?
ありがとう!