f# - 项目Euler＃14尝试失败，并显示StackOverflowException

我最近开始在Scala中解决Project Euler问题，但是当我遇到问题14时，我遇到了StackOverflowError，因此我在F＃中重写了我的解决方案，因为(被告知)F＃编译器与Scala的不同(产生Java字节码)不同，将递归调用转换为循环。
因此，我要问的是，下面的代码在达到113000以上的某个数字后，怎么可能引发StackOverflowException？我认为递归不一定要是尾递归才能进行翻译/优化，对吗？
我尝试几次重写代码，但没有成功。我真的不想用命令式的命令来编写代码，我也不认为我可以将len函数变成尾递归的，即使那是妨碍其优化的问题。

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＃并不是很精通，也没有费心寻找简化它并使它更加优雅的方法(至今)。

谢谢。

最佳答案

如果我将所有的int更改为int64并在每个数字文字后附加一个L(例如-1L)，则您当前的代码运行没有错误，并获得了正确的结果。如果实际问题是您溢出了32位整数，那么我不确定为什么会收到StackOverflowException。

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

关于f# - 项目Euler＃14尝试失败，并显示StackOverflowException，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4558703/