Looping is recursion

Fork this

https://github.com/iloveponies/looping-is-recursion

Here are the instructions if you need them. Be sure to fork the repository behind the link above.

Starting out

Clojure has a form called loop. But it’s not actually a looping construct, it is recursive in nature. Let’s start with some examples.

This is the standard recursive factorial:

(defn recursive-factorial [n]
  (if (zero? n)
      1
      (* n (recursive-factorial (dec n)))))

Like we’ve seen in the chapter on recursion, this is a linear recursive process, that is, it constructs an expression linear in size to its input, n. When the base case is reached, we will have the expression (* n (* (dec n) (* ... (* 3 (* 2 (* 1 1))) ...))). This also means that the amount of memory taken by recursive-factorial is \(\mathcal{O}(n)\).

We can make this computation more efficient by using tail recursion. A function is tail recursive when its return value is calculated directly by a recursive call. recursive-factorial is not tail recursive, because the value of the recursive call (recursive-factorial (dec n)) is not returned directly, but given to *.

We’ll now introduce a tail recursive version of recursive-factorial and then look at how its evaluation differs from the evaluation of recursive-factorial.

In order to make factorial tail-recursive we introduce an accumulator.

(defn helper [acc n]
  (if (zero? n)
    acc
    (helper (* acc n) (dec n))))

(defn accumulating-factorial [n]
  (helper 1 n))

helper uses the return value of its recursive call directly as its return value. That means it is tail recursive. Let’s see how it evaluates:

    (accumulating-factorial 5)
;=> (helper 1 5)
;=> (helper (* 1 5)   (dec 5)) => (helper 5 4)
;=> (helper (* 5 4)   (dec 4)) => (helper 20 3)
;=> (helper (* 20 3)  (dec 3)) => (helper 60 2)
;=> (helper (* 60 2)  (dec 2)) => (helper 120 1)
;=> (helper (* 120 1) (dec 1)) => (helper 120 0)
;=> 120

Now we see that evaluating helper does not grow the expression we are computing. This is because we do not add any structure around the recursive call. That keeps the structure of the returned expression constantly (helper ...) and the parameters vary. Since we can’t build the computation as a recursive expression, we’re instead computing each step explicitly into the acc accumulator.

This is a linear iterative process or just linear iteration (compared to linear recursion). It is indeed similar to iteration in imperative languages.

Let’s rewrite factorial one more time, now using a new construct called recur. recur means “recursively call this function (that we’re in)”, with the additional restriction that the recursion must be tail recursion.

(defn recur-factorial [number]
  (let [helper (fn [acc n]
                 (if (zero? n)
                   acc
                   (recur (* acc n) (dec n))))]
    (helper 1 number)))

Here we’ve replaced the recursive call helper with recur. Since recur can only occur in a tail position (that is, a call whose return value is directly returned), the compiler knows the recursion is actually iteration, and can compile it into a simple loop. This is called tail-call optimization.

We have also moved helper inside recur-factorial and defined it with fn. This was not possible before, because an anonymous function has no name to call recursively. But as we now make the recursive call with recur, we can use fn. The benefit of this is that the helper function was never supposed to be visible to anyone and now it isn’t.

Again, because recur guarantees tail-call optimization, it can be present only in a tail position. While this might seem awkward, it’s an advantage too. When we’ve placed recur in a non-tail position where Clojure can not perform tail-call optimization, the compiler will give us an error. This indicates that our request to optimize the tail call is not possible. If the compiler allowed recur outside tail positions (and simply performed regular recursion), we would not know whether tail-call optimization actually took place or not.

In short: recur guarantees tail-call optimization by requiring that the call to it is in an optimizable position.

(power 2 2)  ;=> 4
(power 5 3)  ;=> 125
(power 7 0)  ;=> 1
(power 0 10) ;=> 0

(last-element [])      ;=> nil
(last-element [1 2 3]) ;=> 3
(last-element [2 5])   ;=> 5

(seq= [1 2 4] '(1 2 4))  ;=> true
(seq= [1 2 3] [1 2 3 4]) ;=> false
(seq= [1 3 5] [])        ;=> false

Because defining the sort of helper functions like helper in our factorial is quite usual in functional programming, there is a utility called loop for this. The previous code could be written like this:

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

Let’s dissect that. A loop begins with a sequence of bindings, just like in a let. As in let, you can use destructuring in the names.

  (loop [acc 1
         n down-from]

This introduces the variables acc and n and gives them initial values. n gets its value from the parameter loopy-factorial.

After this comes the body of the loop, which is exactly the same as the body of the helper function above:

    (if (zero? n)
      acc
      (recur (* acc n) (dec n)))))

Inside a loop we can think of a recur meaning “go to the start of the loop, and give the variables these new values”. So after that recur call the variable n gets the new value (dec n), and acc gets the new value (* n acc). That is, calling recur either calls the function iteratively, or iterates a loop, whichever is innermost.

This kind of corresponds to the following Java loop (if you want to look at it that way):

int n = number;
int acc = 1;
while (true) {
    if (n <= 1) {
        break;
    } else {
        acc = n * acc;
        n = n - 1;
    }
}
return acc;

(find-first-index zero? [1 1 1 0 3 7 0 2])                    ;=> 3
(find-first-index zero? [1 1 3 7 2])                          ;=> nil
(find-first-index (fn [n] (= n 6)) [:cat :dog :six :blorg 6]) ;=> 4
(find-first-index nil? [])                                    ;=> nil

(avg [1 2 3])   ;=> 2
(avg [0 0 0 4]) ;=> 1
(avg [1 0 0 1]) ;=> 1/2 ;; or 0.5

(parity [:a :b :c])           ;=> #{:a :b :c}
(parity [:a :b :c :a])        ;=> #{:b :c}
(parity [1 1 2 1 2 3 1 2 3 4] ;=> #{2 4}

(toggle #{1 2 3} 1) ;=> #{2 3}
(toggle #{2 3} 1) ;=> #{1 2 3}

(fast-fibo 0) ;=> 0
(fast-fibo 1) ;=> 1
(fast-fibo 2) ;=> 1
(fast-fibo 3) ;=> 2
(fast-fibo 4) ;=> 3
(fast-fibo 5) ;=> 5
(fast-fibo 6) ;=> 8

(cut-at-repetition [1 1 1 1 1])
;=> [1] doesn't have to be a vector, a sequence is fine too
(cut-at-repetition [:cat :dog :house :milk 1 :cat :dog])
;=> [:cat :dog :house :milk 1]
(cut-at-repetition [0 1 2 3 4 5])
;=> [0 1 2 3 4 5]

Performance viewpoint

Tail recursion is efficient. This is because the compiler can replace it with a goto (this is called tail-call optimisation. So a tail-recursive function is about exactly as fast as the corresponding loop.

However, this doesn’t exactly apply in the Java Virtual Machine. This is because the security model of the JVM makes tail-call optimisation hard. This is why Clojure uses the recur construct: it is guaranteed that a call to recur gets optimised. I’ll say that again. When you use recur, Clojure generates an actual loop as JVM bytecode.

The one →