PurelyFunctional.tv Newsletter 357: Tip: recursion vs iteration

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 onc e 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