рекурсивный вызов, приводящий к переполнению

Я пытаюсь решить второй вопрос проекта Эйлера. Почему приведенный ниже код приводит к переполнению стека? Я использую recur, поэтому он не должен хранить все рекурсивные вызовы в стеке.

(defn sum
  [[a b]]
  [b (+ a b)])

(defn fib-r
  ([n] (fib-r n 0 [0 1]))
  ([n s [a b]]
     (if (= n 0)
       s
       (let [[c d] (sum [a b])
             e (if (even? c) c 0)
             f (+ s e)]
         (recur (dec n) f [c d])))))

(fib-r 4000000)

clojure
person murtaza52    schedule 21.06.2012    source источник
comment
Вы выполняете рекурсию 4000000 раз (т. е. вычисляете 4-миллионное число Фибоначчи), вопрос касается только чисел Фибоначчи менее 4000000.   -  person huon    schedule 21.06.2012

Ответы (2)


arrow_upward
6
arrow_downward

вы получаете целочисленное переполнение (а не переполнение стека). Если вы используете BigInts (литералы BigInt заканчиваются на N), то Clojure с радостью вычислит правильный результат:

(defn fib-r                                                                                          
  ([n] (fib-r n 0N [0N 1N]))                                                                     
  ([n s [a b]]                                                                                     
     (if (= n 0N)                                                                            
       s                                                                            
       (let [[c d] (sum [a b])                                               
             e (if (even? c) c 0N)                               
             f (+ s e)]                             
         (recur (dec n) f [c d])))))
#'autotestbed.core/fib-r                                                                                               
autotestbed.core> (fib-r 40000)
1158997879999727672946417013062336891791160667328280503727448.... big number
person Arthur Ulfeldt    schedule 21.06.2012
comment
Только что пробовал с 4млн, а реп просто зависает. Это потому, что вычисления слишком велики? - person murtaza52; 21.06.2012
comment
Я рассчитал время, и на моем рабочем столе это заняло 7,28 минуты. - person Arthur Ulfeldt; 21.06.2012

arrow_upward
1
arrow_downward

Это было большое изменение, внесенное в Clojure 1.3 (см. http://dev.clojure.org/display/doc/Enhanced+Primitive+Support для получения дополнительной информации) автоматическое продвижение примитивных типов не происходит автоматически.

Вам не нужно везде использовать BigInts, как предлагает Артур Ульфельдт, вместо этого вы можете использовать автоматическое продвижение плюс операцию +':

(defn sum [[a b]] [b (+' a b)])

Это подойдет.

Что касается случая с 4 миллионами - да, это вычисление велико. Вы можете изменить свою функцию fib-r следующим образом:

(defn fib-r
  ([n] (fib-r n 0 [0 1]))
  ([n s [a b]]
     (if (and (< 0 n) (zero? (mod n 100000)))
       (println n))
     (if (= n 0) s
       (let [[c d] (sum [a b])
             e (if (even? c) c 0)
             f (+ s e)]
         (recur (dec n) f [c d])))))

чтобы увидеть, как быстро это происходит.

person Paweł Łoziński    schedule 21.06.2012