PurelyFunctional.tv Newsletter 356: Tip: convert recursion to iteration
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
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
(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
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
fib(0) = 1 which would make that first
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 🍿
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
This week's challenge
Every natural number can be expressed as a product of primes. For
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.