PurelyFunctional.tv Newsletter 362: Tip: double recursion

Written by Eric Normand. Published: January 27, 2020.

Issue 362 - January 27, 2020 · Archives · Subscribe

Clojure Tip 💡

double recursion

A few issues ago, I deconstructed the parts of recursion that you need in order for it to work. They were 1) a base case 2) progress toward the base case. But did you know that you can have multiple base cases, making progress toward some or all of them in each recursion? This is how you can implement algorithms that in other paradigms might be nested loops. Let me demonstrate.

If I want to recurse through a doubly-nested vector, I might traditionally use nested for loops. But we can do it with a single recursive function.

(defn print-double-nested
  "v is a doubly nested vector, like [[1 2 3] [4 5 6]]"
  [v]
  (loop [inner [] outer v]
    (cond
      (not (empty? inner))
      (let [[f & rst] inner]
        (println f)
        (recur rst outer))

      (not (empty? outer))
      (let [[f & rst] outer]
        (recur f rst))

      :else
      :done!)))

Let's just gather information about this function. First, there are three cases. One is a base case (when both inner and outer are empty). Second, there are two recursive cases. When inner is not empty, the recursion makes progress on inner but not outer. When outer is not empty, the recursion "refills" inner and makes progress on outer. Eventually, we will run out of nested vectors, and the whole thing will end. Two recursive calls, each making progress toward the same base case.

But you can have multiple base cases!

In the challenge from last week, we needed to find the closest "gapful number" to a given number. The closest number could be smaller or bigger. In the case that both are equally close, we are supposed to favor the smallest one.

Here is a doubly-recursive solution:

(defn closest-gapful2 [n]
  (loop [high? true low (dec n) high n]
    (if high?
      (if (gapful? high)
        high
        (recur false low (inc high)))
      (if (gapful? low)
        low
        (recur true (dec low) high)))))

Note that there are two base cases, one that returns high and one that returns low. These are returned if we have found a gapful number, which we will eventually.

We are also making progress in our two recursive cases. One increments high, making it higher, and the other decrements low, making it lower. In this way, we alternate between making progress up and making progress low. Eventually, one will be a gapful number, and we return.

I often use double recursion like this to traverse known structures. I'm not sure if it's something I can recommend you do. Should I keep doing them? They often seem too complex and clever. Anyway, it's something you may encounter and find useful. What do you think about all this?

Relevant courses 📚

If you like recursion, laziness, and reduce, check out these courses.

Book update 📖

Chapter 6 is out! Buy it now: Grokking Simplicity.

I'm still working on Chapter 7, but it is "content complete". I've said everything I need to in the chapter. Now it's just about final polish: layout, design, editing, and, what my editor calls "over authoring" where you layer on helpful information to make it easier for the reader.

Chapter 7 is about stratified design. And I'm very happy diving into the reality of design. The iterations, the false starts, the dead ends, and sometimes, rarely, finding something sublime. But most of the time you just make it easy to read so you can come back later.

Since Chapter 6 just came out, it will be about a month before Chapter 7 comes out.

You can buy the book and use the coupon code TSSIMPLICITY for 50% off.

Podcast episode🎙

I've revamped the format of my podcast. If you like reading old computer science papers to really understand how we got here (and sometimes uncover old gems), this podcast is for you. Subscribe!

In the first episode of the season, we read a paper from 1987 by Abelson and Sussman, the authors of SICP, called * Lisp: A language for stratified design*. The paper asks the question: "What is Lisp good for?" Read the paper, then follow along on the podcast.

The next episode comes out next Monday. We are reading The Early History of Smalltalk.

Clojure Challenge 🤔

Last week's challenge

The challenge in Issue 361 was a function to find the closest "gapful number" to a given integer. You can see the submissions.

You can leave comments on these submissions in the gist itself. Please leave comments! We're all here to learn.

This week's challenge

Parse query parameters

URLs can have optional query parameters. They are the key-value pairs that follow the path.

Write a function that takes a URL (represented as a string) and parses out the query parameters into a hashmap.

Notes:

The query string is the string containing the query parameters. It appears after the ? and before a #. Ex: /search?q=clojure#page2
The keys and values are URL Encoded. You can use java.net.URLDecoder/decode to decode them.
The key-value pairs are separated by &. Ex: a=1&b=2
Each key-value pair contains the key, followed by =, followed by the value. Ex: a=1

Bonus:

Query parameters can contain duplicate keys. Handle them gracefully.

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 sub mission, let me know.

Rock on!
Eric Normand