Loops in Clojure

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:

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

To implement this algorithm, we’ll need a few auxiliary functions; one for calculating the absolute value, one for calculating the average of two numbers and one for checking if a guess is within the tolerance. None of these is recursive, so we can just give their code:

(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.