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?

Answer 1

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

Answer 2

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.