The One Thing You Need to Learn Recursion
An old, somewhat abused quip goes:
To understand recursion, you need to understand recursion.
It's the kind of joke that only programmers, mathematicians, or logicians find funny. It also isn't true.
Like many other things, the one thing you need to understand recursion is practice. Write a lot of simple recursive functions. Then write a lot more. Then write some more complex recursive ones. And so on. But how do you do it? I have a trick. It's a book. It's short (less than 200 pages), compelling, and will teach you much more than how to write recursion. It will also introduce you to some of the most foundational concepts in Computer Science, such as the Y combinator, interpreters, combinators, and the halting problem.
This marvelous little book is called The Little Schemer.¹ In the "Preface", almost at the very beginning, the authors emphatically state:
The goal of the book is to teach the reader to think __ recursively.
If you go through The Little Schemer, recursion will become a familiar way of thinking about problems. But, in the meantime, you will learn a veritable treasure trove of basic ideas. Moreover, the book is written in a very peculiar style, forcing you to work through its problems and assimilate its concepts.
In what follows, I will give a brief overview of what recursion is and why you should learn it. Then I will introduce you to the book and explain why it's an outstanding tool that will make you a better programmer.
Note: if you are a complete beginner, and you aren't into more abstract topics, this might not be the best book for you. If you are at the stage in which you want to learn to code and have something to show, my suggestion is come back to the book later, when you feel comfortable in one Programming language. Then again, if your interests in programming are more philosophical or theoretical, this might be a good starting point.
Recursion: why it matters
Recursion is daunting; the word "magic" gets thrown around a lot. Advice to beginners abound. I read someone advising beginners to "trust the magic" – or something to that effect. You might get told to learn how the call stack works. Sure, it's useful, even fundamental: yet, not the best way to become proficient or even comfortable using recursion. I know none of those suggestions truly worked for me. What did work was, you guessed it, practice. I may not be a master of recursion. But certainly, I am now more than comfortable with using it. As a matter of fact, I sometimes now struggle not to write recursive functions even when I could use simpler, more efficient solutions.
I suspect people struggle with recursion because it somehow (mistakenly) suggests that an infinite regress is going on behind the scenes. It seems as though recursion is akin to what happens when two mirrors are placed in front of themselves: the first reflects the reflection of the second which reflects the reflection of the first which reflects …. It's an effect that was – incidentally – cleverly employed by many artists and designers. But that's not at all what happens.
A recursive function is a function that calls itself. For example, here are two (slightly different) functions that consume an array or list of integers and return its sum, in Javascript and Python:
function sumAllNums(listNums) {
if (listNums.length === 0) return 0;
return listNums.shift() + sumAllNums(listNums);
}
console.log(sumAllNums([1, 2, 3, 4]));
// 10def sum_all_nums(lst):
if len(lst) == 0:
return 0
return lst[0] + sum_all_nums(lst[1:])
print(sum_all_nums([1, 2, 3, 4]))
# 10Both functions will:
- Check if the input is empty, in which case they will return 0 (the base case)
- Otherwise, they will add the first item of the input to the result of calling that function of the remainder of the input (all of the items except the first one) (the recursive call).
A recursive function will keep calling itself infinitely, unless it hits the base case. When that happens, the recursive calls stop – which is why we avoid an infinite loop.
That may be all well and good: but why should I become proficient in writing recursive functions? After all, anything you can write recursively, you can do with iteration in a while loop. Why struggle with this magic-seeming tool? That's a sensible question. Off the top of my head I can think of at least the following three reasons:
- Algorithms and data structures: many foundational algorithms are recursive in nature (think "divide and conquer"). Some data structures are best represented recursively (think graphs or trees)
- Even within machine learning recursive structures and algorithms are more common than one might think (not to mention AI in general, where they are ubiquitous). For example, the implementation of decision trees is inherently recursive.
- Functional programming: some say functional languages are slowly growing in popularity. That may or may not be true. Certainly, more and more "mainstream" languages such as Python or Javascript now support functional programming. Moreover, some widely used libraries and frameworks (such as React) are by and large based on functional practices. Given that the functional paradigm has no notion of assignment (a little more on that later), recursion is absolutely paramount for it
- Understanding: recursion forces you to reduce problems to other, smaller-sized, problems. That is one of the most valuable skills you may develop as a programmer.
Unfortunately, I can't think of a single extensive resource dedicated to practicing recursion. That's where The Little Schemer comes in.
The best book for learning recursion
Judging by the title, The Little [Scheme](https://en.wikipedia.org/wiki/Scheme(programminglanguage))r (henceforth, TLS) should be a book about the programming language Scheme, one of the many that compose the family of LISPs. So why would someone want to learn a LISP or Scheme specifically? The thing is, the title is a misnomer. Scheme is a language that is very well suited to teaching certain fundamentals of computer science² – and for the purposes of TLS the syntax you need is so sparse you can seriously pick it up in a few minutes. You can safely see it more as a pedagogical tool than as a full-fledged language³.
Speaking of pedagogy: the book employs a quirky style. It is written in two columns, as some sort of Socratic dialogue between a student and a teacher. This is how it begins:
Is it true that this is an atom? atom
It doesn't give you definitions – it asks the reader questions (often in the form of exercises) and then provides answers (or solutions). It takes some getting used to, but it's strangely effective.
What does recursion have to do with all this? Well, in TLS the authors use Scheme in a way that doesn't support variable assignment or iterations. There are no while or for loops. This means that if you have to write a function what will, for example, check if a certain number is contained in a list or array of numbers, you cannot do something like (in Python):
def is_contained(num, list_nums):
for ix in range(len(list_nums)):
if list_nums[ix] == num:
return True
return False
print(is_contained(1, [2, 3, 4, 1]))
# TrueInstead, you have to think recursively:
- There is a base case in which the list will be empty and the function should return False
- Otherwise, you select the first item of the list and check it for equality against the given number; if they match the function returns True. If they do not, (recursively) call the function with the remainder of the list.
This is how you write everything in TLS. Scheme operates on only two basic syntactic elements:
- _atom_s: one or more alphanumeric characters
- lists: zero or more atoms or lists enclosed in parentheses.
To write functions such as the above all you need is:
- a programming construct to test if two expressions are the same
- another test to check if a a list is empty
- selectors for the first element of a list and for the remainder of the list
- a way to express conditionals (such as
if)
For more complex functions, you also need a constructor to build lists. Together with some means of defining functions, that's all. This is why almost all of the syntax you need is introduced in the first chapter, in less than 10 breezy pages (the exception is the list-building constructor cons which gets introduced in chapter 3). The first three chapters walk you through many simpler recursive functions.
By the time you reach Chapter 4 you should have become familiar with the basic design pattern for writing recursive functions which operate on lists: functions such as the one above that check for whether a particular item is a member of a list. Or functions that replace the first (or all) occurrences of a given item in a list with another.
That knowledge is subsequently applied to building the basic arithmetic operations from first principles. Again, this is done by using recursion on numbers and resorting to provided primitives, which increment and decrement a number by 1. For example, addition of two numbers n and m is defined as:
- base case: if m is zero, return n
- Otherwise, recursively return the result of applying the addition function to incremented n and decremented m.
Chapters 5 and 6 introduce recursive functions on arbitrarily deeply-nested lists: lists that may contain lists that may, in turn, contain lists, and so on. Basically, you rewrite all of the functions from the previous chapters so that they work in the "deeper" cases.
This knowledge finds its concrete application in Chapter 6, where you write an interpreter for arithmetic expressions. Let me emphasize: we are 100 pages into the book. We began with no knowledge of Scheme and the sparsest syntax – yet here we are, building an interpreter that evaluates operations we defined. If you are interested in the more theoretical aspects of programming, chances are you will find this very rewarding and exciting.
Chapter 7 is devoted to set-theoretic constructs, relations, and functions, all of which, again, is left for the reader to discover in the course of reading through the student-teacher dialogue.
Chapter 8 is perhaps the least satisfying of the book: it is remarkably steep, and it's hard to see the point of some of the constructs introduced here. The crux of it seems to be the introduction of continuations, but I must confess that I struggled with this chapter (as, apparently, have many others).
Like the preceding one, Chapter 9 is challenging: a lot of fundamental concepts get introduced in a few pages which lead up to a discussion of the applicative-order Y combinator. I did enjoy it a lot, but it took me quite a few attempts and the help of some online resources (see below) to get through it. By the way, if you ever wondered what on Earth the Y combinator is (while we are on the topic of recursion): it's (very coarsely) how you define recursion in a language that has no way to name functions (and hence, a language in which all functions are anonymous – such as lambda functions in Python). Being able to grok the Y combinator is an enriching experience and, for me, one of the book's highlights.
The final chapter puts it all together when you end up writing a Scheme interpreter in Scheme. Let it sink in: with only a few primitives, and using only recursion you are writing an interpreter for a language by bootstrapping that language itself.
I hope I was able to convey the excitement I felt while going through TLS. And I hope you will reach out to me to share your experience.
Additional resources
- I have a GitHub repo (in progress!) where I am publishing notes, the solutions, and a fairly extensive test-suite for the book in Racket here
- Another GitHub repo (also in Racket) I like: https://github.com/bmitc/the-little-schemer
- And yet another one: https://github.com/willprice/little-schemer
- A negative (yet, not entirely off-base) review of the book: https://inventwithpython.com/blog/2018/12/09/book-review-the-little-schemer/) to counterbalance my enthusiasm
- An excellent blog post on the Y combinator if you get stuck
[1] Friedman, Daniel, P, Felleisen, Matthias [The Little Schemer], The MIT Press, Cambridge, MA, 1986, 4th edition 1996 (https://mitpress.mit.edu/9780262560993/the-little-schemer/). Originally published as The Little LISPer.
[2] In fact one of (if not the) most well-regarded computer science books of all time, Structure and Interpretation of Computer Programs utilizes Scheme.
[3] This is not significant but I should mention that my implementation of the exercises in TLS is not in Scheme but in Racket, which is basically a successor to Scheme.
