CODEWITHSUNDEEP
loopsclojuretail-recursion
DPA
DPA

Reputation: 154

Endless loop recur

I'm learning Clojure and I've just started on Project Euler and I've run into a problem I cannot figure out. Here is my code:

(defn largest_prime_factor
  [x]
  (if (prime? x) x)
  (loop [running x divider 2]
    (if (= 0 (mod running divider))
      (let [d (/ running divider)]
        (if (prime? d)
          d
          (recur d 2)))
      (recur x (inc divider)))))

(largest_prime_factor 12)  ;works
(largest_prime_factor 49)  ;works
(largest_prime_factor 147) ;Endless loop!

I realise that this might not be the most efficient way to find the largest prime factor but what I'm trying to figure out is why it gets stuck in a loop. Obviously I'm using loop-recur the wrong way but what am I doing wrong?

Upvotes: 2

Views: 149

Answers (2)

A. Webb
A. Webb

Reputation: 26466

A couple of things

(defn largest_prime_factor
  [x]
  (if (prime? x) x)                 ; #1
  (loop [running x divider 2]
    (if (= 0 (mod running divider))
      (let [d (/ running divider)]
        (if (prime? d)
          d
          (recur d 2)))
      (recur x (inc divider)))))    ; #2

  1. The extra closing parenthesis makes this a self-contained if without an else clause. This has no bearing on the infinite loop, but would give the wrong answer (1) for a prime input (unless you start your divider at 1 instead, in which case you can omit this initial test).

  2. This line should recur with running rather than x, otherwise you have not factored out the divisor and the prime? test will ever after be false. This is why you wind up in an infinite loop.

Upvotes: 3

Hendekagon
Hendekagon

Reputation: 4643

(if (prime? x) x)

I think you mean 

(if (prime? x) x
  (loop [...

Upvotes: 3

Related Questions