アッカーマン関数の解法

Question

F#、関数型言語ともに初心者です。
F#でアッカーマン関数を書いてみましたが 数字が大きくなった場合にスタックオーバーフローが発生しています。
末尾再帰にすることで最適化されて実行できるようになると思っておりますが、どのように書き換えれば良いかわかりません。

末尾再帰最適化により解決できる問題なのでしょうか？
また、書き換え後のソースをご教授いただきたいです。

アッカーマン関数

###ソースコード

    let rec ack  m n  = 
        match (m,n) with
            | (0,_) -> n + 1   
            | (_,0) -> ack (m-1) 1
            | (_,_) -> ack (m-1) (ack (m) (n-1))

    printfn "%d" (ack 4 1)

Answer 1

以下のサイトに、末尾再帰バージョンがあります。
Ackermann in F# - devCatharsis

以下、引用です。

let ackermann m n =
    let rec ackermann m n acc =
        match m, n, acc with 
        | 0, _, m :: tl -> ackermann m (n + 1) tl 
        | 0, n, _ -> n + 1 
        | m, 0, _ -> ackermann (m - 1) 1 acc
        | m, n, _ -> ackermann m (n - 1) ((m - 1)::acc)
    ackermann m n []

以下のサイトにも、別バージョンがありました。
algorithm - Is this implementation tail-recursive - Stack Overflow

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

いずれにしても、スタックは使わないまでも、メモリは使うので、
メモリ不足になる可能性はありますね。