Why do I get stackoverflow error?

[Andy Smith]

Hi,

I am working through the 4clojure questions, I have a few different solutions to problem 87 but all of them run out of stack space. I tried to convert to using recur but I still have the problem. Why does this fail for large n?

((fn pascal ([n] (pascal n [1])) ([n row] (if (= n 1) row (recur (dec n) (map (partial reduce +) (partition 2 1 (concat [0] row [0]))))))) 500)

Andy

[Andy Smith]

Correction problem #97 I mean

[Mars0i]

I don't get a stack overflow error, I get ArithmeticException integer overflow.  It's trying to compute an integer that's too big.  Try changing [1] to [1M] in (pascal n [1]). 

[Mars0i]

Oops--I do get a stack overflow error if I give it 959 or greater as the argument, instead of 500.  It looks like the error is not from the explicit recursion, but is due to concat.  Someone who knows more than I do will have to explain this.

user=> ((fn pascal ([n] (pascal n [1M])) ([n row] (if (= n 1) row (recur (dec n) (map (partial reduce +) (partition 2 1 (concat [0] row [0]))))))) 959)
StackOverflowError   clojure.core/concat/fn--3923 (core.clj:678)
(user=> (pst)
StackOverflowError
    clojure.core/concat/fn--3923 (core.clj:678)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)
    clojure.core/concat/cat--3925/fn--3926 (core.clj:687)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)
    clojure.core/partition/fn--4309 (core.clj:2834)
    clojure.lang.LazySeq.sval (LazySeq.java:42)

On Monday, February 3, 2014 3:19:36 PM UTC-6, Andy Smith wrote:

[Leif]

As Mars0i says below, this is due to concat; more specifically, since map, partition, and concat all return lazy sequences, with recursion you are constructing a large chain of nested lazy sequences, as explained here:

http://stackoverflow.com/questions/5294055/why-am-i-getting-a-stackoverflow

More in-depth analysis of a similar problem:

https://www.ksmpartners.com/2014/01/clojure-lazy-seq-and-the-stackoverflowexception/

I applaud you for testing your solution with large n to make sure it's robust; since the 4clojure test cases all have n <= 11, my solution, and the solutions of those I follow, including many very good clojure programmers, also failed at large n.  Keep up your good habits.

[Andy Smith]

Ok thanks, thats really helpful. The second link suggests using doall, which seems to do the trick :

((fn pascal ([n] (pascal n [1M])) ([n row] (if (= n 1) row (recur (dec n) (map (partial reduce +) (doall (partition 2 1 (concat [0] row [0])))))))) 500)

However you do lose the laziness, but here the laziness is not needed ...

[Andy Smith]

Similarly this works for my non-recursive effort, which I think is more concise :

(fn [n] (nth (iterate (fn [r] (map (partial reduce +) (doall (partition 2 1 (concat [0N] r [0]))))) [1]) (dec n)))

[Sean Corfield]

Another option is:

((fn pascal ([n] (pascal n [1M])) ([n row] (if (= n 1) row (recur (dec n) (mapv (partial reduce +) (partition 2 1 (cons 0 (conj row 0)))))))) 500)

Because row is a vector you can conj 0 to the end (quickly) and cons 0 to the front (quickly) and then mapv makes sure you get a vector back.

Sean