Why am I getting a StackoverflowError on a function without explicit recursion

Question

I am trying to generate a relatively small (1296 elements) list of vectors essentially enumerating 4 base 6 digits from [0 0 0 0] to [5 5 5 5]

[0 0 0 0], [1 0 0 0] ... [5 0 0 0], [0 1 0 0] ... [5 5 5 5]

Currently what I have is:

(letfn [(next-v [v]
          (let [active-index (some (fn [[i e]] (when (> 5 e) i)) 
                                   (map-indexed vector v))]
            (map-indexed #(cond
                           (> active-index %1) 0
                           (= active-index %1) (inc %2)
                           :else %2)
                         v)))]
  (last (take 1290 (iterate next-v [0 0 0 0]))))

This works but it eventually blows the stack.

What am I doing here that causes the StackOverflowError? How can I structure my code so that it is "safe"? Is there a better way of doing what I am trying to do?

two other similar questions: http://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow http://stackoverflow.com/questions/24958907/why-does-reduce-give-a-stackoverflowerror-in-clojure — event_jr, Jul 19 '15 at 18:21

Michiel Borkent · Answer 1 · 2015-07-19T15:14:14.110

5

The way I would solve this is:

(def my-range
  (for [i (range 0 6)
        j (range 0 6)
        x (range 0 6)
        y (range 0 6)]
    [i j x y]))

(nth my-range 1295) ;;=> [5 5 5 5]

Generalized:

(defn combine [coll]
  (for [i (range 6)
        j coll]
    (conj j i)))

(combine (map list (range 6)))
(combine (combine (map list (range 6))))
(combine (combine (combine (map list (range 6)))))

(def result (nth (iterate combine (map list (range 6))) 3))

edited Jul 19 '15 at 15:14

answered Jul 19 '15 at 13:41

Michiel Borkent

34,228
15
86
149

Thank you. Not sure why I wasn't seeing that. – Garrett Rowe Jul 19 '15 at 14:34
What about the more general solution where the length of the vector is variable? – Garrett Rowe Jul 19 '15 at 14:44
@GarrettRowe Oops, made a mistake. Edited again. – Michiel Borkent Jul 19 '15 at 15:14
1

You can also use `(clojure.math.combinatorics/selections (range 0 6) 5)` – ClojureMostly Jul 19 '15 at 20:44

score 4 · Accepted Answer · answered Jul 19 '15 at 13:50

This is due to lazyiness in the iterated function body. Notice that the result returned by the first call of next-v is passed to next-v again, before being evaluated (because its a lazy seq), then next-v returns again an unevaluated lazy-seq which will again be passed to it.

When you realize the final lazy seq, to produce the first element all the chained seqs have to be realized to get through to your initial [0 0 0 0]. This will blow the stack.

Stuart Sierra wrote a nice article on this with more examples: http://stuartsierra.com/2015/04/26/clojure-donts-concat

You could simply wrap the map-indexed call in the let body in a vec.

Finding a more generic algorithm to your problem is recommended though.

Why am I getting a StackoverflowError on a function without explicit recursion

2 Answers2