Project Euler #14 attempt fails with StackOverflowException

Question

I recently started solving Project Euler problems in Scala, however when I got to problem 14, I got the StackOverflowError, so I rewrote my solution in F#, since (I am told) the F# compiler, unlike Scala's (which produces Java bytecode), translates recursive calls into loops. My question to you therefore is, how is it possible that the code below throws the StackOverflowException after reaching some number above 113000? I think that the recursion doesn't have to be a tail recursion in order to be translated/optimized, does it? I tried several rewrites of my code, but without success. I really don't want to have to write the code in imperative style using loops, and I don't think I could turn the len function to be tail-recursive, even if that was the problem preventing it from being optimized.

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

NOTE: I am aware that the code below is very far from optimal and several lines could be a lot simpler, but I am not very proficient in F# and did not bother looking up ways to simplify it and make it more elegant (yet).

Thank you.

Not being that knowledgeable in F# I'm not posting this as an answer, but I'm fairly confident that F# only optimizes some tail recursions with the stack frame dropping call or into loops, and can not optimize non-tail recursive calls (how would this be done anyhow?). — jball, Dec 29 '10 at 23:19
Most automatic conversion of recursion to loops does only work for tail-recursion. — Don Roby, Dec 29 '10 at 23:20
@jball: Well, since all recursive functions can be rewritten to be non-recursive using loops, I thought that maybe the compiler is smart enough to do that rewrite itself :) — PeterParameter, Dec 29 '10 at 23:48
and soon the computers will replace the programmers completely :) — jball, Dec 29 '10 at 23:50

score 3 · Accepted Answer · answered Dec 30 '10 at 00:40

Your current code runs without error and gets the correct result if I change all the int to int64 and append an L after every numeric literal (e.g. -1L). If the actual problem is that you're overflowing a 32-bit integer, I'm not sure why you get a 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

Quick test shows that the int64 version terminates at a recursive depth of 525. The 32bit version crashes at a depth of around 20000 with a negative `num` — gradbot, Dec 30 '10 at 00:57
Now that really _is_ weird, because I kept getting StackOverflowException. Anyway, thank you very much, I did not realize that the intermediate numbers could get _much_ larger than 1000000. — PeterParameter, Dec 30 '10 at 00:58

Project Euler #14 attempt fails with StackOverflowException

1 Answers1