The Beauty of Recursion

Recursion is one of the most fascinating and elegant concepts in Computer Science. The feeling of figuring out recursive algorithms & data structures is a special one for a software developer. In this context, there is probably no better source than The Little Schemer book for both understanding and satisfying your recursive appetite.

Although this might seen like just a book about Scheme, I’d say this is mostly a book about thinking recursively. Based entirely on questions, puzzles, and exercises which guide you gradually from the most basic concepts, like atoms and s-expressions, to the most mind-blowing ones, like the Y Combinator, the teaching method is quite engaging and very unusual when compared to traditional programming books.

The Little Schemer seems to be a popular book among Clojure developers like my friend Marcos. Even though there are idiomatic differences to Scheme, it is totally possible to implement all the exercises in the book using Clojure. Here is my test-driven version: github.com/vvgomes/little-schemer

The Y Combinator

By far, the most difficult challenge in the book is the Y Combinator. In summary, the goal is to describe recursion formally using Lambda Calculus theory, which in practice means pretty much defining recursive functions with anonymous functions only. In the example given in the book we move from a traditional recursive function definition like this:

(def length
  (fn [l]
   (cond
     (null? l) 0
     :else (add1 (length (cdr l))))))

… to a Y Combinator based definition, like the following:

(def Y
  (fn [le]
    ((fn [f] (f f))
      (fn [f] (le (fn [x] ((f f) x)))))))

(def length
  (Y
    (fn [length]
      (fn [l]
        (cond
          (null? l) 0
          :else (add1 (length (cdr l))))))))

There are around 17 steps involved to get from the initial to the final stage (you can see all the steps here) and you usually don’t get it in the first time. Not even in the second one. However, if after the third time you still don’t get it, I’d recommend you to take a look at this very good explanation by Jim Weirich and try again. That’s what I did.

Does your hat still fit?

Perhaps not after such a mind stretcher.

Vinicius Gomes

Software Developer

Tweet Share