PurelyFunctional.tv Newsletter 358: Tip: recursion rollercoaster

Issue 358 - December 30, 2019 · Archives · Subscribe

Clojure Tip 💡

recursion rollercoaster

I have a confession to make. Recursion scares me. It's like a rollercoaster every time I do it. But like a rollercoaster, if you're prepared, it can be really fun.

How do you prepare?

Well, the safety harness of any recursion is the base case. The base case is the last case you expect to be encountered. For instance, in Fibonacci, there are two base cases, 0 and 1.

(defn fib [n]
  (cond
    (= 0 n)
    0

    (= 1 n)
    1

    :else
    (+' (fib (- n 1)) (fib (- n 2)))))

That base case does not do any recursion itself. In this case, they are each a literal number. You could also do a last bit of work, or return some variable. The important thing is that they define the end of the recursion. Without an end, your recursion would go on forever!

Base cases are often easy to define. They are often the easiest cases to write! It's one of the power skills of recursion: you can define the easy cases first, and they will protect you from infinite recursion. Base cases are often the empty list (in case you're recursing through a list), 0 (if you're recursing through numbers), or some otherwise easy case for your data type.

Because base cases are important and easy, I start with those. They make my rollercoaster ride exciting instead of scary.

Now, we've gone through the base case safety equipment. How do we know we're actually going to get to the base case? Well, the other thing you need in recursion is progress toward your base case. Basically, every recursive call needs to get you one step closer to a base case.

We can see that again in Fibonacci. Our recursive calls both reduce n before calling fib. They are making n closer to the base cases. We can reason easily that we will eventually get to a base case in both recursive calls.

(defn fib [n]
  (cond
    (= 0 n)
    0

    (= 1 n)
    1

    :else
    (+' (fib (- n 1)) (fib (- n 2)))))

If you didn't make progress, you could go into an infinite loop as well. You'd never reach your base case. You need to make progress in every recursive call!

Well, that's about all I have to say about recursion. Write your base cases and you'll be safe. Make progress in each recursion. And enjoy the ride!

If you'd like to learn more about recursion, I have a video course on it. In it, we go over several examples you are familiar with, including map and filter. We talk about important details, like how recursion interacts with laziness in Clojure. It's a good introduction to the topic. Check out Recursion 101.

Follow-up 🙃

Folks, I for real have the best readers.

Three whole people responded to my discussion of recursion vs iteration, saying that SICP Chapter 1 has the best explanation of the difference between them. Thanks to Paul Roush, Josef Jelinek, and Juraj Martinka.

I also said my implementation of the prime factorization "got a Sieve of Eratosthenes for free". I wasn't clear. What I meant was that there was no additional code to generate primes. Val Waeselynck helped me realize that my algorithm performs significantly worse than a Sieve, so it's not at all free.

Thanks for being there! You make this newsletter great.

Clojure Media 🍿

People often ask what web framework they should use in Clojure. A common response is "just put one together yourself". That's my preferred method as well. However, it's a pretty daunting task for a beginner to the ecosystem. What's more, there is almost no help out there for making sense of 1) what libraries are available, maintained, and recommended and 2) what pieces are needed to build a stack yourself. To help people with those two problems, I am writing guides to the Clojure web ecosystem. They should culminate in a course for building web apps in Clojure the Clojure way.

I wrote up my recommendation for choosing a Web server in Clojure. It was very hard to write because it is not at all clear what the best choices are. There are compromises in each of them. However, I think I found the best recommendations. Please let me know what you think about it. I want this to be a resource for beginners who aren't as familiar with the Clojure ecosystem. Check out Clojure Web Server Recommendations.

In a related note, Martin Kavalar talks about choosing a web stack for his Clojure project on the Defn Podcast. He noted that he stressed over it way too much. Choosing a web framework in other languages is an important, hard-to-reverse decision. However, choosing individual libraries is not as irreversible in Clojure. Many libraries are interchangeable with a small amount of work. That's a plus, I think, and something I want to remind people of throughout the guides I'm writing. In short "Don't Panic! You can change your mind later."

Clojure Challenge 🤔

Last week's challenge

The challenge in Issue 357 was to implement dependency ordering for a project management app. You can see the submissions.

This week's challenge

unmix string

Oh no! My strings have been mixed up. Each pair of letters has been swapped.

Here are examples: "eHllo" should be "Hello". "lCjorue" should be "Clojure".

Write a function to unmix these strings. If the length of the string is odd, the last character is not altered.

(unmix "aHpp yeN weYra !eS eoy uni2 20 0):")

Implement and run the line above to decode the secret message!

Thanks to to this site for the challenge idea!

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