プロジェクトオイラー＃14の試行がStackOverflowExceptionで失敗する

Question

私は最近、問題14になったときにStackOverflowErrorを取得したので、F＃でソリューションを書き直しました。コンパイラは、Scala（Javaバイトコードを生成する）とは異なり、再帰呼び出しをループに変換します。 したがって私の質問は、113000を超える数に達した後で、以下のコードがStackOverflowExceptionをスローする可能性がありますか？ I は、再帰が翻訳/最適化のためにテールの再帰である必要はないと思いますか？ 私はコードをいくつか書き直しましたが、成功しませんでした。私は実際にループを使って命令型のコードを書く必要はなく、len関数をtail-recursiveにすることはできないと思っています。

module Problem14 = 
    let lenMap = Dictionary<'int,'int>() 
    let next n = 
     if n % 2 = 0 then n/2 
     else 3*n+1 

    let memoize(num:int, lng:int):int = 
     lenMap.[num]<-lng 
     lng 

    let rec len(num:int):int = 
     match num with 
     | 1 -> 1 
     | _ when lenMap.ContainsKey(num) -> lenMap.[num] 
     | _ -> memoize(num, 1+(len (next num))) 

    let cand = seq{ for i in 999999 .. -1 .. 1 -> i} 
    let tuples = cand |> Seq.map(fun n -> (n, len(n))) 
    let Result = tuples |> Seq.maxBy(fun n -> snd n) |> fst 

注：私は以下のコードは非常に遠くに最適な、いくつかのラインからあるずっと簡単かもしれないことを承知していますが、私はF＃で非常に熟達していないですし、それを簡素化し、作る方法を探して気にしませんでしたよりエレガントな（まだ）。

ありがとうございます。

Answer 1

あなたの現在のコードはエラーなしで実行され、私はすべてのintint64に変更し、すべての数値リテラル（例えば-1L）後Lを追加する場合、正しい結果を取得します。実際の問題が32ビット整数をオーバーフローさせている場合は、なぜStackOverflowExceptionが発生するのか不明です。知識豊富なF＃で、私は答えとしてこれを投稿していないんだけど、私はF＃が唯一のスタックフレーム落ちコールまたはループにいくつかの尾の再帰を最適化し、非最適化することができないことをかなり確信していることをされていない

module Problem14 = 
    let lenMap = System.Collections.Generic.Dictionary<_,_>() 
    let next n = 
     if n % 2L = 0L then n/2L 
     else 3L*n+1L 

    let memoize(num, lng) = 
     lenMap.[num]<-lng 
     lng 

    let rec len num = 
     match num with 
     | 1L -> 1L 
     | _ when lenMap.ContainsKey(num) -> lenMap.[num] 
     | _ -> memoize(num, 1L+(len (next num))) 

    let cand = seq{ for i in 999999L .. -1L .. 1L -> i} 
    let tuples = cand |> Seq.map(fun n -> (n, len(n))) 
    let Result = tuples |> Seq.maxBy(fun n -> snd n) |> fst