When writing programs with loop / recur, its not always clear to me how to arrive at a solution from first principles. Initially loop / recur seems like a bit of a mystery.

Consider the problem of adding up numbers from 1. E.g. The base case is 0.

[0] -> 0 [1] -> 1 [1 2] -> 3 [1 2 3] -> 6 [1 2 3 4] -> 10

The classical solution to the problem might have a function with 2 arities (1 and 3 arguments in this case). It might be invoked as `(add-up 3)`

with an expected answer of 6. This invokes the first arity: `(add-up 3 0 0)`

, subsequent recursions will then invoke via the 2nd arity.

(defn add-up ([limit] (add-up limit 0 0 )) ([limit current sum] (if (< limit current) sum (add-up limit (+ 1 current) (+ current sum)))))

The problem with the above function is that it could blow the stack because Clojure is not naturally tail recursive. It must be told to be tail recursive by means of `recur`

. Refactor it to use `recur`

in the tail call position:

(defn add-up ([limit] (add-up limit 0 0 )) ([limit current sum] (if (< limit current) sum (recurlimit (+ 1 current) (+ current sum)))))

It works now, and will not blow the stack but it's not idiomatic. Refactor again by removing the arities, replace the 2nd arity call by `loop`

with with the function argument no longer passed in. The two other arguments, which had previously been initialised in the first arity call are now initialised at the `loop`

(defn add-up [limit] (loop [current 0 sum 0] (if (< limit current) sum (recur (+ 1 current) (+ current sum)))))

This is now idiomatic Clojure. Testing:

user=> (add-up 0) 0 user=> (add-up 4) 10 user=> (add-up 1000000) 500000500000

## No comments:

Post a Comment