recursive call resulting into overflow

Question

I am trying to solve the project euler 2nd question. Why is the below code resulting into stack overflow ? I am using recur so it should not be storing all the recursive calls on the stack.

(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)

You are recursing 4000000 times (i.e. computing the 4 million-th Fibonacci number), the question only asks for Fibonacci numbers under 4000000. — huon
– huon, Commented Jun 21, 2012 at 1:57

Arthur Ulfeldt · Accepted Answer · 2012-06-21 02:17:45Z

6

your getting an integer overflow (rather than a stack overflow) If you use BigInts (BigInt literals end with N) then Clojure will happily compute the correct result:

(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

answered Jun 21, 2012 at 2:17

Arthur Ulfeldt

91.7k30 gold badges205 silver badges285 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

murtaza52 Over a year ago

I just tried with 4 million, and the repl just hang. Is it because the computation is lo large ?

Arthur Ulfeldt Over a year ago

I timed it and it took 7.28 min on my desktop

Paweł Łoziński · Accepted Answer · 2012-06-21 17:31:35Z

This was a big change made in Clojure 1.3 (see http://dev.clojure.org/display/doc/Enhanced+Primitive+Support for details) auto-promotion of primitive types does not happen automatically.

You don't have to use BigInts everywhere as Arthur Ulfeldt suggests, you can instead use auto-promoting plus operation +':

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

This will do.

In regards to the 4 million case - yes this computation is large. You can modify your fib-r function like this:

(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])))))

to see how fast this is going.

Collectives™ on Stack Overflow

recursive call resulting into overflow

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related