# PurelyFunctional.tv Newsletter 357: Tip: recursion vs iteration ### From OO to Clojure Workshop!

Watch my free workshop to help you learn Clojure faster and shift your paradigm to functional.

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 🍿

Paredit --- a Visual Guide

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

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]])