Clojure Tail Recursion with Prime Factors

Question

I'm trying to teach myself clojure and I'm using the principles of Prime Factors Kata and TDD to do so.

Via a series of Midje tests like this:

(fact (primefactors 1) => (list))

(fact (primefactors 2) => (list 2))

(fact (primefactors 3) => (list 3))

(fact (primefactors 4) => (list 2 2))

I was able to create the following function:

(defn primefactors 
    ([n] (primefactors n 2))
    ([n candidate] 
        (cond (<= n 1) (list)
              (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate)
              :else (primefactors n (inc candidate))
        )
    )
)

This works great until I throw the following edge case test at it:

(fact (primefactors 1000001) => (list 101 9901))

I end up with a stack overflow error. I know I need to turn this into a proper recur loops but all the examples I see seem to be too simplistic and only point to a counter or numerical variable as the focus. How do I make this recursive?

Thanks!

Answer 1

Here's a tail recursive implementation of the primefactors procedure, it should work without throwing a stack overflow error:

(defn primefactors 
  ([n] 
    (primefactors n 2 '()))
  ([n candidate acc]
    (cond (<= n 1) (reverse acc)
          (zero? (rem n candidate)) (recur (/ n candidate) candidate (cons candidate acc))
          :else (recur n (inc candidate) acc))))

The trick is using an accumulator parameter for storing the result. Notice that the reverse call at the end of the recursion is optional, as long as you don't care if the factors get listed in the reverse order they were found.