Fun with recursion and The Little Schemer

The first thing I did at Recurse was spend a couple weeks trying to get comfortable with writing functionally and recursively in Scheme.

One of the fun things about the book The Little Schemer is it has concise thought-provoking definitions. Like this one:

How is a [natural] number defined? It is either zero or it is one added to a rest, where rest is again a number.

Numbers as recursive increment / decrement

The thought-provoking bit is that this definition is inherently recursive, To illustrate it, we only need to assume that we have 0 and a way to add 1.

What's 4? 4 is 1 + 3.

Okay, but what's 3? 3 is 1 + 2.

And what's 2? 2 is 1 + 1.

What's 1? 1 is 1 + 0.

And what's 0?

0 is just 0, it's a primitive that we build on.

In programming terms, this means any natural number can be arrived at by calling a recursive function until you hit 0. The Little Schemer is all about getting you to understand thinking recursively this way and practicing writing recursive functions in Scheme.

You can write an addition function for natural numbers, if you have primitive operations for adding one, subtracting one, and testing whether a number is zero. Here's what that might look like in Python, assuming we have three primitive functions incr(n) that returns n + 1; decr(n) that returns n - 1; and is_zero(n) that returns boolean:

def add(n, m):
   if is_zero(m):
      return n
   else:
     return incr(add(n, decr(m)))

In english, we might define add(n, m) like "n if m is zero, otherwise 1 plus adding n to m-1."

What's this look like in Scheme? In the book they call the increment function add1, and decrement is sub1, and the zero test is zero?. The syntax is different and takes getting used to, but this means exactly the same as the python version above:

(define +
 (lambda (n m)
   (cond
     ((zero? m) n)
     (else (add1 (+ n (sub1 m)))))))

In either version, if you walk through an example like 4 + 3, you'll see it's similar to the recursive definition of 4 above:

What's 4 + 3? It's 1 + (4 + 2). What's 4 + 2? It's 1 + (4 + 1). What's 4 + 1? It's 1 + (4 + 0). What's 4 + 0? It's 4.

If you put it all on one line, 4 + 3 is: 1 + (1 + (1 + (4))).

If it occurs to you that 1 + 10,000 requires 10,000 function calls, you'd be right. This is considered normal in languages like scheme. Don't worry about it :)

Lists, recursive

Here's another short definition:

All lists are either: empty, an atom consed onto a list, or a list consed onto a list.

That may sound like gibberish without knowing some Lisp terminology.

cons is just a function that adds an element to the front of list.

An "atom" just means something that isn't list-like: it doesn't have distinct elements, it's eg a number. Like a leaf in a tree.

Another way to phrase this without cons might be: A list is either empty, or it's an atom added to the front of another list, or it's a list added to the front of another list.

Another, more conventional way to put this definition in English might be: Lists are either empty, or contain some mixture of atoms and lists.

The important thing about the definition is again that it's recursive. The statement is true both of any specific list you're looking at, and of all lists contained within it, and all lists contained within those, etc.

The reason I find the original recursive definition helpful is because it helps me think about how to work with lists recursively. The three possible characteristics of a list inform how to write every recursive function that works with lists, because there are three things to always check:

  • Always check if the list is empty, aka the null list, and stop recursing.
  • Check if the first element is an atom, and handle it appropriately.
  • Or if it's a list, handle that appropriately.

Finally, recursively call the function on the remainder of the list after the first element. (What if there aren't any more elements? Then the recursive call will hit the first case (the list is empty) and immediately return.)

The book spells out some "commandments" about these in more detail.

For example, what do you return when you get an empty list and stop recursing? It depends on what your function is supposed to do. If it returns a count of interesting data, you would typically return 0 when the list is empty. If your function returns a new possibly different list, then you would typically return an empty list when the passed in list is empty. There are great examples of these in the book, and enough repetition to plant these patterns firmly in your head.

Tags