Clojure Tail Recursion with Key Factors

Question

I am trying to teach myself clojure, and I am using the principles of Prime Factors Kata and TDD for this.

Through a series of Midje tests:

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

I managed 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 fine until I throw the following edge test on it:

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

I get an error. I know that I need to turn this into the correct recur loops, but all the examples that I see seem too simplistic and only point to a counter or a numerical variable as the focus. How to make it recursive?

Thanks!

Answer 1

Here's the tail recursive implementation of the primefactors procedure, it should work, not throw an 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 uses the battery option to store the result. Note that a reverse call at the end of a recursion is optional, as long as you don't care if the factors get listed in the reverse order as they were found.

Answer 2

The second recursive call is already in the tail positions, you can just replace it with recur .

 (primefactors n (inc candidate)) 

becomes

 (recur n (inc candidate)) 

Any overload function opens an implicit loop block, so you do not need to insert it manually. This should already improve the stack situation, as this branch will be more widely used.

First recursion

 (primefactors (/ n candidate)) 

not in the tail position, as its result is transmitted to conj . To put it in the tail position, you will need to collect the primary coefficients in the extra argument of the accumulator, to which you conj get the result from the current recursion level, and then go to recur for each call. You will need to configure the termination condition to return this battery.

Answer 3

A typical way is to turn on the battery as one of the function arguments. Add a version of the 3-arity definition to the function definition:

 (defn primefactors ([n] (primefactors n 2 '())) ([n candidate acc] ...) 

Then change the form (conj ...) to a call (recur ...) and pass (conj acc candidate) as the third argument. Make sure you pass the three recur arguments, i.e. (recur (/ n candidate) 2 (conj acc candidate)) , so you call the primefactors 3-arity version.

And in the case (<= n 1) you need to return acc , not an empty list.

I can go into details if you cannot understand the solution for yourself, but I thought that I should give you a chance to try to figure it out first.

Answer 4

This function really should not be tail recursive: instead, it should create a lazy sequence. In the end, it would be nice to know that 4611686018427387902 is unrelated (it is divided into two), without having to collapse the numbers and find that its other simple coefficient is 2305843009213693951 ?

 (defn prime-factors ([n] (prime-factors n 2)) ([n candidate] (cond (<= n 1) () (zero? (rem n candidate)) (cons candidate (lazy-seq (prime-factors (/ n candidate) candidate))) :else (recur n (inc candidate))))) 

The above is a rather unimaginable translation of the algorithm you posted; Of course, there are better algorithms, but it gives you the correctness and laziness and corrects stack overflow.

Answer 5

A recursive, battery-free solution with a lazy sequence:

 (defn prime-factors [n] (letfn [(step [n div] (when (< 1 n) (let [q (quot n div)] (cond (< q div) (cons n nil) (zero? (rem n div)) (cons div (lazy-step q div)) :else (recur n (inc div)))))) (lazy-step [n div] (lazy-seq (step n div)))] (lazy-step n 2))) 

Recursive calls built into lazy-seq are not evaluated before iterating the sequence, eliminating the risks without resorting to using the battery.