# PurelyFunctional.tv Newsletter 357: Tip: recursion vs iteration

Sign up for weekly Clojure tips, software design, and a Clojure coding challenge.

*Issue 357 - December 23, 2019 ·
Archives ·
Subscribe*

## Clojure Tip 💡

*recursion vs iteration*

Astute reader and all-around awesome community member Ray asked a very
important question: isn't `loop/recur`

recursion and not iteration?

We do have some iterative constructs in Clojure. There's `dotimes`

and
`doseq`

and even a `while`

loop. We also have recursive constructs.
There's regular recursion (a function calling itself) and explicit tail
recursion (`recur`

). So, what's the deal? Why did I call my
`loop/recur`

version of Fibonacci *iterative*?

It's a great question, and the short answer is I was using the terms
*iterative* and *recursive* a little loosely. Let's look at the
recursive definition of Fibonacci.

```
(defn fib [n]
(cond
(= 0 n)
0
(= 1 n)
1
:else
(+' (fib (- n 1)) (fib (- n 2)))))
```

This version of the function clearly defines Fibonacci in terms of
itself. That's what I'm refering to as *recursive*.

Now let's look at the version that I'm calling *iterative*.

```
(defn fib5 [n]
(if (< n 2)
n
(loop [i 2 f2 0 f1 1]
(if (= i n)
(+' f1 f2)
(recur (inc i) f1 (+' f1 f2))))))
```

`loop`

is just a shorthand for what would be another function call.
Let's look at the longhand.

```
(defn fib5-helper [n i f2 f1]
(if (= i n)
(+' f1 f2)
(recur n (inc i) f1 (+' f1 f2))))
(defn fib5 [n]
(if (< n 2)
n
(fib5-helper n 2 0 1)))
```

That is to say that `loop`

is a short way of defining a new function
that is itself recursive and calling it. In this case it is called
`fib5-helper`

. But `fib5`

is no longer defined in terms of itself, so it
is not recursive.

Is `fib5-helper`

recursive? Technically, yes. But I'm so used to
thinking of tail recursive functions like this as tight loops that I
used the term *iterative* instead. `fib5-helper`

probably gets compiled
down to something similar to this Java code:

```
long fib5Helper(long n, long i, long f2, long f1) {
while(true) {
if(n == i)
return f1 + f2;
i++;
long tf1 = f1;
f1 = tf1 + f2;
f2 = tf1;
}
}
```

That's how I think of `loop/recur`

. Tail recursion gets converted into
an iterative loop that has a value (since it's an expression). It's a
mistake to not call it recursion, though. I really should have said
"convert recursion to tail recursion". That would have been more
accurate.

Thanks, Ray!

## Follow-up 🙃

Ray also mentioned that using the letter `l`

for one-character variable
names is a really bad idea because many fonts make it hard to
distinguish between `l`

and `1`

(el and one). Good call, Ray! There are
so many great letters, `l`

should be avoided.

It reminded me of this Java puzzler: https://youtu.be/wbp-3BJWsU8?t=2584

BTW, watching that (and a few other Java Puzzler videos) in order to find the puzzle that I remembered reminded me of how lucky we are in Clojure. Remember how easy it is to get things wrong in Java next time you're complaining about Clojure.

## Clojure Media 🍿

This animated guide to the operations of Paredit is so fun to watch.

## Clojure Challenge 🤔

### Last week's challenge

The challenge in Issue 356 was to implement prime factoring. You can see the submissions.

I wanted to bring something up. My version was very good on many measures. It has very little nesting, it's concise, and it works!

```
(defn factor
([n]
(factor 2 [] n))
([p ps n]
(cond
(= 1 n)
ps
(zero? (rem n p))
(recur p (conj ps p) (quot n p))
:else
(recur (inc p) ps n))))
```

However, I've been thinking about mathematical algorithms, especially those that have been worked over so many times by many developers. Sometimes, there is a clever bit of math done on paper that doesn't show up in the code.

For instance, I know that once I factor out all of the 2s, the resulting number will never be divisible by 4 (or any other even number). Likewise for 3. Once I factor out all the 3s, it will never be divisible by 6 or 9. This means I get a Sieve of Eratosthenes "for free". No need to generate the list of primes separately.

But the more I look at it, the more concerned I am with it. There's something that is too clever about it. That mathematical reasoning is not evident in the code. And there are certain assumptions that follow from it. For instance, it means I have to start at 2 and work up, just like you would for a Sieve of Eratosthenes.

Here's what's bothering me. The code is simple because it contains a lot of assumptions. Those assumptions are based on mathematical reasoning that is not captured in the code. And the mathematical reasoning is not easy to do. I got lucky and had seen this algorithm before. If I hadn't learned it, what are the chances I'd get it myself? Am I worried about nothing?

### This week's challenge

*task dependencies*

Let's say you're writing a project management app. A user will have a bunch of tasks to do and each task might depend on other tasks. Your challenge is to write a function that, given tasks and dependencies, gives at least one order for the tasks such that no task is done before its dependencies are done.

```
(def tasks [:clean-breakfast :shoes :socks :cook-breakfast
:eat-breakfast])
(def dependencies [[:socks :shoes] ;; socks come before shoes; shoes depend on
socks
[:cook-breakfast :eat-breakfast] ;; cooking comes before
eating
[:eat-breakfast :clean-breakfast]])
(defn order-tasks [tasks dependencies]
;; you fill this out
)
(order-tasks tasks dependencies) => [:socks :shoes :cook-breakfast
:eat-breakfast :clean-breakfast]
```

As usual, please reply to this email and let me know what you tried. I'll collect them up and share them in the next issue. If you don't want me to share your submission, let me know.

Rock on!

Eric Normand