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

### Exercise 1

Write the function `(power n k)`

that computes the mathematical expression \(n^k\).

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

### Exercise 2

Compute the last element of a sequence.

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

### Exercise 3

Write the function `(seq= a-seq b-seq)`

that compares two sequences for equality.

```
(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;
```

### Exercise 4

Implement the function `(find-first-index [predicate seq])`

that returns the first index in `seq`

for which `predicate`

returns true, or `nil`

if no such index exists.

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

### Exercise 5

Implement the function `(avg a-seq)`

that computes the average of a sequence.

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

*Hint:*You need to keep track of multiple things in the loop.

### Exercise 6

Write the function `(parity a-seq)`

that takes in a sequence and returns a *set* of those elements that occur an odd number of times in the sequence.

```
(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}
```

*Hint:* Recall the fuction `(toggle set elem)`

from Structured data

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

### Exercise 7

Write the function `(fast-fibo n)`

that computes the `n`

th fibonacci number using `loop`

and `recur`

. Do not use recursion.

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

*Hint:* to avoid recursion, you need to keep track of \(F_{n-1}\) and \(F_n\) in the loop.

### Exercise 8

Write the function `(cut-at-repetition a-seq)`

that takes in a sequence and returns elements from the sequence up to the first repetition.

```
(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]
```

*Hint:* Remember that `conj`

ing onto a vector appends the element.

*Hint:*A set might be helpful

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