CODEWITHSUNDEEP
clojure
zcfrank1st
zcfrank1st

Reputation: 523

why this code is wrong ? How does 'recur' work?

I don't know why the code below is wrong:

(defn factorial [n]
  (loop [n n
         acc 1]
    (if (zero? n)
      acc
      (recur (* acc n)(dec n)))))

 (= 1 (factorial 1))

How does recur work?

Upvotes: 1

Views: 148

Answers (1)

Thumbnail
Thumbnail

Reputation: 13473

The arguments to the recur are the wrong way round.

  • n should become (dec n)
  • acc should become (* acc n)

So it should be 

(recur (dec n) (* acc n))

We can recast the given algorithm to see what's going on inside it.

If we represent the pair of arguments as a vector, the function that generates the next pair is

(fn [[n acc]] [(* acc n) (dec n)])

We can generate the endless sequence of possible pairs for a given noby applying iterate to the function above, starting with [no 1]. 

(fn [no]
  (iterate (fn [[n acc]] [(* acc n) (dec n)]) [no 1]))

Applying this to 1 generates

([1 1] [1 0] [0 0] [0 -1] ...)

We stop at element 2, the first with an initial 0, returning the other 0.

If we put the arguments the right way round, we can get the proper factorial thus: 

(defn factorial [no]
  ((comp second first)
         (drop-while
           (comp not zero? first)
           (iterate (fn [[n acc]] [(dec n) (* acc n)]) [no 1]))))

This returns the second element of the first pair in the sequence with a zero first (Duh!).

Hopelessly overcomplicated for normal use, but does it work? 

=> (map factorial (range 6))
(1 1 2 6 24 120)

Yes.

Upvotes: 3

Related Questions