Попытка Project Euler # 14 завершилась неудачей со StackOverflowException - PullRequest
Новая
       17

Попытка Project Euler # 14 завершилась неудачей со StackOverflowException

3 голосов
/ 30 декабря 2010

Я недавно начал решать проблемы Project Euler в Scala, однако, когда я добрался до проблемы 14, я получил StackOverflowError, поэтому я переписал свое решение на F #, поскольку (как мне сказали), компилятор F #, в отличие от Scala (который производит Javabytecode), переводит рекурсивные вызовы в циклы.Поэтому мой вопрос к вам, как это возможно, что код ниже генерирует исключение StackOverflowException после достижения некоторого числа выше 113000?Я думаю , что рекурсия не должна быть хвостовой рекурсией, чтобы ее можно было перевести / оптимизировать, не так ли?Я попытался несколько переписать мой код, но безуспешно.Я действительно не хочу писать код в императивном стиле с использованием циклов, и я не думаю, что мог бы превратить функцию 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 # и не стал искатьспособы упростить и сделать его более элегантным (пока).

Спасибо.

1 Ответ

3 голосов
/ 30 декабря 2010

Ваш текущий код работает без ошибок и получает правильный результат, если я изменю все 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
...