CODEWITHSUNDEEP
recursionclojuresum
user8926565
user8926565

Reputation: 87

How to write this as a recursive Clojure function?

I'll illustrate what I want to do using Python (I want to write this in Clojure). I have this function:

def f(n):
    s=0
    for d in range(1,n+1):
        s+=d*(n//d)
    return(s)

Which is basically looping from d=1 to n inclusive, and summing up the values of d times the floor of n/d.

In Clojure I want to make this a recursive function. Python equivalent:

def f(d, n):
    if d == 0: return 0
    else: return d*(n//d) + f(d-1, n)

and then I'd call the function with f(n, n).

I am trying this:

(defn f
     ([n] (f n n))
     ([d n]
      (if (> d 0)
         (recur (dec d) n)
        0)))

But I don't know if this is right so far or where to slip in the sum or how to do it, etc.

Upvotes: 1

Views: 687

Answers (3)

Thumbnail
Thumbnail

Reputation: 13473

If you look at your Clojure f function, the [d n] arity recurs with

  • d decremented and
  • n unchanged

... until d is zero, when it returns 0.

If we write this arity as a distinct local function, using letfn, we can drop the unchanging n argument, picking it up from the f argument: 

(defn f [n]
  (letfn [(g [d]
           (if (> d 0)
               (recur (dec d))
               0))]
    (g n)))

This produces the wrong answer of course, always returning 0: 

(f 10)
=> 0

But we can see where to put the sum in:

(defn f [n]
  (letfn [(g [d]
           (if (> d 0)
               (+  (* d (quot n d)) (g (dec d)))
               0))]
    (g n)))

We have to revert the recur to an explicit recursive call to g, as it is surrounded by the +.

But at least it works: 

(f 10)
=> 87

In Clojure I want to make this a recursive function.

Don't. I've done it above just to show you where the calculation fits in.

Explicit recursion is rare in idiomatic Clojure. Better use the functions that encapsulate its common patterns. I won't repeat what Carciginate has given, but once you get used to threading macros, I think you'll find the following clear and concise: 

(defn f [n]
  (->> (range 1 (inc n))
       (map (fn [d] (* d (quot n d))))
       (reduce +)))

By the way, a reasonable analogue of your Python code is

  (defn f [n]
    (loop [s 0, d 1]
      (if (> d n)
          s
          (recur (+ s (* d (quot n d))) (inc d)))))

Upvotes: 6

Carcigenicate
Carcigenicate

Reputation: 45750

I managed to get 3 ways working. Unfortunately, this algorithm doesn't seem to lend itself to nice recursion.

To get safe recursion, I had to introduce a third parameter. I just couldn't get it arranged so the recur was in the tail position. I also decided to count up instead of down. I don't think there's anything left field here, although it did get quite long unfortunately. 

(defn f3
  ([n] (f3 n 1 0))
  ([n d s]
   (if (> d (inc n))
     s
     (recur n (inc d)
            (+ s (* d (quot n d)))))))

(f3 10)

If unsafe recursion is ok, this can be simplified quite a bit. Instead of adding multiple argument lists, I decided to allow d to be defaultable using & [d?]] and a check later down. I tend to avoid adding multiple argument lists since par-infer has a difficult time handling the indentation required to make it work. This trick isn't possible with the first way due to how recur handles var args. It only works if you're not using recur, or you do use recur, but only destructure 1 var-arg. 

(defn f2 [n & [d?]]
  (let [d (or d? 1)]
    (if (> d (inc n))
      0
      (+ (f2 n (inc d)) (* d (quot n d))))))

(f2 10)

Unless you really need recursion though, I'd just write it as a map and reduction:

(defn f1 [n]
  (reduce + 0
    (map #(* % (quot n %)))
      (range 1 (inc n)))))

(f1 10)

Which to me is about as neat as it gets (without using a threading macro. See Thumbnail's answer).

Upvotes: 1

Terminus
Terminus

Reputation: 949

Try this:

(defn f
 ([n] (f n n))
 ([d n]
  (if (> d 0)
     (+ (* d (quot n d)) (recur (dec d) n))
    0)))

Upvotes: -1

Related Questions