We saw in the post on recursion in Clojure that the language doesn’t support any loops in the conventional sense. Rather, iteration must be done using recursion, with tail recursion the favoured mechanism. It may come as a surprise that Clojure contains a function called **loop**. It’s a bit cheeky, since the Clojure loop is really just a shorthand way of doing recursion. To see how this works, first recall the implementation of the power function (for raising a number x to an integer power y) we provided earlier:

(defn power ([x y] (power x y 1)) ([x y current] (if (= y 0) current (if (> y 0) (recur x (- y 1) (* x current)) (recur x (+ y 1) (/ current x))))))

The recursion consists of two steps: an initialization step in which the recursive part of the function is called, with **current** set to 1 as a starting point, and the recursive part of the function in which the answer is built up by successively multiplying or dividing (depending on whether y is positive or negative) **current** by x.

The **loop** function allows us to merge the initialization step into the recursive part of the function, so that only one argument list is required, rather than the two we used above. Let’s see how **power** is rewritten using **loop**.

(defn power [x y] (loop [exponent y current 1.0] (if (= exponent 0) current (if (> exponent 0) (recur (- exponent 1) (* x current)) (recur (+ exponent 1) (/ current x))))))

We see that this version of **power** has a single argument list, taking as input x and y. The **loop** begins on line 2. A loop’s first argument is a vector (in square brackets) of symbol-value pairs. For each pair, the first element is bound to the second element. So in this example, **exponent** is bound to the value of y, and **current** is bound to 1.0.

The second argument of a **loop** is a statement that is run. Apart from the use of the symbol **exponent** in place of y, this code is identical to our earlier version. The key point is that when a **recur** function is encountered, the recursion starts again with the statement within the **loop**, not with the function that contains the loop. Thus here, the recursion reverts back to line 5, not line 1.

The loop has a superficial resemblance to a **for** loop in Java. The loop begins with the call to **loop**, and the pairs in the initialization vector are like the initialization condition in a **for** loop. The statement following the initialization is like the body of statements in a **for** loop. However, whereas a **for** loop has a specific termination condition stated in its first line, a **loop** can terminate only if the statement it runs recursively contains an anchor step that stops the recursion. In our example here, that condition is the test to see if **exponent** is zero on line 5. Just as it is possible to write an infinite loop in Java, so it is possible in Clojure if there is no anchor step, or the anchor step is never reached. As always, it’s up to the programmer to ensure this doesn’t happen.

We can expand this example a bit by applying the **power** function in another function. A method originally due to Newton for finding the nth root of a number goes like this. To find the nth root of **number** to within a tolerance **tol**:

- Make an initial
**guess**of 1.0 for the root. - Calculate
**guess**to the nth power. - Calculate the absolute value of the difference between
**number**and**guess**to the nth power. - If this difference is less than
**tol**, return**guess**as the answer. - If not, take the average of
**guess**and**number/(guess^(n-1))**as the next**guess**and repeat from step 2.

(defn abs "Absolute value of argument" [n] (if (< n 0) (* n -1) n)) (defn avg "Average of two arguments" [a b] (/ (+ a b) 2)) (defn within-tol? "Is guess^n within tolerance of number?" [number n tol guess] (let [diff (- (power guess n) number)] (if (< (abs diff) tol) true false)))

Hopefully, these are fairly straightforward so we don’t need to comment on them. (OK, there are probably more succinct ways in which these could be implemented in Clojure, but I’m sticking to the elementary techniques we’ve looked at so far.)

One thing is worthy of note, however. Note that the name of the function for testing the tolerance ends with a question mark. Clojure allows more characters to be part of symbol names than most languages. The rules are

- Symbol names may contain any alphanumeric character (although they cannot begin with a number).
- Names may also contain the characters * + ! – _ and ?
- A colon : is also allowed, but not at the beginning or end of the name, and it is not allowed to be repeated within the name. (Actually, colons are probably best avoided…)

For example, a function that returns a boolean result can end in a question mark, since it is determining whether some condition is true or false. The **within-tol?** function above does just that.

Anyway, with these functions in place, we can write the main function that uses a **loop** to calculate the nth root of a number:

(defn nth-root "Calculates the nth root of number to a tolerance tol" [number n tol] (loop [guess 1.0] (if (within-tol? number n tol guess) guess (recur (avg guess (/ number (power guess (- n 1))))))))

The function takes 3 arguments: the number, the value of n that specifies which root is to be calculated, and the tolerance to which we want the answer. The loop initializes **guess** to 1.0. The body of the loop first checks to see if the guess is within the tolerance (this is the anchor step that will stop the recursion), and, if so, returns the current **guess** as the answer.

If the answer isn’t yet good enough, a recursive call is made to the loop with the new guess as specified in the algorithm above.

As you might expect, the program takes longer to run as you either increase n or decrease the tolerance **tol**. This is due to the mathematics behind the algorithm: Newton’s method isn’t the most efficient method for finding roots if a high precision is needed. However, it’s a good exercise in recursion.

## Comments

I’m a Clojure newbie. I was doing Clojure Koans ( http://clojurekoans.com/ ) and came upon a Koan that used Loop. In googling for “loop in clojure”, I found this page among the results and ended up reading it end to end. While I’m not strong enough in mathematics to follow the last (and crucial) bit of Newton’s algorithm, I learnt a lot about Clojure from reading this article. Cheers!

## Trackbacks

[…] line 3, we begin a loop. We discussed loops in an earlier post. Here we initialize lower and upper as instructed by the algorithm. You might wonder, by the way, […]

[…] how recursion can be implemented efficiently (that is, without stack overflow), and also how the loop special form can be used to simulate a loop in an imperative language. These techniques work well if we’re […]