PurelyFunctional.tv Newsletter 356: Tip: convert recursion to iteration

Issue 356 - December 16, 2019 · Archives · Subscribe

Clojure Tip 💡

convert recursion to iteration

In the last issue, I showed how to use memoization to speed up a Fibonacci calculation. I mentioned that memoization was nice because you could wrap the nice mathematical definition and achieve acceptable performance without changing your code. You could solve performance issues by converting the recursion to iteration, which may be harder to read.

Samantha Atkins asked why it's harder to read. She suggested calculating the values forward. It's a good question and I'll try to answer it.

Well, I don't know if it is harder to read, so let's do it now. However it turns out, converting recursion to iteration is an important skill.

For reference, here is the memoized, recursive version:

(declare fib)
(def fib
  (memoize
   (fn [n]
     (cond
       (= 0 n) 0
       (= 1 n) 1
       :else   (+' (fib (- n 2)) (fib (- n 1)))))))

If we look closely, this recursive function works backwards. It starts at n and decrements it in each recursion, eventually landing on 0 or 1, which are the base cases.

We could go forward, starting from 0 and working to n. We can calculate them and add them to the end of a vector. That means each element of the vector at position i is fib(i).

(defn fib2 [n]
  (loop [vals [0 1]]
    (if (contains? vals n)
      (get vals n)
      (let [c (count vals)
            l1 (get vals (- c 1))
            l2 (get vals (- c 2))]
        (recur (conj vals (+' l1 l2)))))))

It's actually a cool solution. We're using the contains? function asking "does this vector contain an answer for n?" If it doesn't, we add one more answer and try again.

In writing this, I thought it was kind of awkward to get the last two values out of the vector. (Try it, because I tried several ways and this was the best I could find.) This got me thinking: we want the last two elements, and that's easy in a list. So let's convert this to use a list.

(defn fib3 [n]
  (if (zero? n)
    0
    (loop [vals (list 1 0)]
      (if (< n (count vals))
        (first vals)
        (let [[l1 l2] vals]
          (recur (conj vals (+' l1 l2))))))))

This is my attempt at that. It's much easier to destructure the first 2 elements from the list and add them. I think the test for the base case is a little difficult. I had to think about it, and I'll probably want to check that it's correct the next time through. Plus, I had to check for zero, because the loop doesn't handle that case correctly.

It strikes me that I have seen a different definition of Fibonacci that made fib(0) = 1 which would make that first if unnecessary.

Then I got to thinking that we don't really need the whole list. We only ever destructure at most two elements from it. So why not just store those two?

(defn fib4 [n]
  (cond
    (= 0 n) 0
    (= 1 n) 1
    :else
    (loop [i 2 l2 0 l1 1]
      (if (= i n)
        (+' l1 l2)
        (recur (inc i) l1 (+' l1 l2))))))

We check those initial two values, then jump into a loop. l2 is the second-to-last element, and l1 is the last. The loop is very tight code. Now, I'm just code golfing, but that cond is kind of verbose. It's basically saying "if n is less than 2, return n."

(defn fib5 [n]
  (if (< n 2)
    n
    (loop [i 2 l2 0 l1 1]
      (if (= i n)
        (+' l1 l2)
        (recur (inc i) l1 (+' l1 l2))))))

Okay, so we converted the recursive version into four different iterative versions. I can't say that any of these are easier or harder than the others in some objective way. But I prefer the recursive version. Whatever way you like best, it's an important skill to be able to convert between them.

Clojure Media 🍿

Clojure Web Server Recommendations

I wrote this small guide to choosing a web server when starting a new Clojure web project. It was very tough to make recommendations. It gave me a newfound appreciation for the beginner experience. Basically, if we tell people "here are some small pieces, put them together however you like", we have to do a better job of teaching them how to choose the pieces and how to put them together.

This article wouldn't be as good as it is if it wasn't for the feedback, you, my wonderful audience gave me. I'm not worthy of so much attention from such wonderful folks. 😍

Clojure Challenge 🤔

Last week's challenge

The challenge in Issue 355 was to implement A-Star. It was quite a challenging problem. You can see my implementation here: submissions.

This week's challenge

Prime factorization

Every natural number can be expressed as a product of primes. For instance, 10 = 2 x 5 and 24 = 2 x 2 x 2 x 3.

Your task is to write a function that takes a number n as an argument and returns a list of its prime factors.

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