Recursion is an extremely powerful idea, occurring in a number of different forms throughout computer science. It is found in programming, mathematical induction, data structures, among other places.
In this short paper we will investigate recursion by considering how it is manifest in simple programs in the language Lisp. In particular, we will consider a program to compute the length of a list.
All recursion starts with the basic idea that a problem can be divided into two parts; the base case and the inductive case. A base case is addressed in a conventional fashion, without reference to recursion at all.
In Lisp, your base case is almost always represented by the empty list. So you begin by asking yourself, how many elements are there in an empty list? The answer, obviously, is zero.
The next step is to figure out a reduction. What is necessary to take an arbitrary problem, and reduce it to a problem that is slightly smaller. In Lisp usually this is done by stripping off the first element of a list, making the recursive call, then doing something with both the first element and the result of the recursive call.
So returning to the problem of finding the length of a list, we have the following situation. We have a list that we know is not empty (that is, it has at least one element). We remove the first element, and ask for the length of the resulting list. Having obtained that value, what is then the length of the original list? The answer, obviously, is that we simply add one to the result of the recursive call.
Combining the two parts by means of an if statement, we get the following pseudo-code description of the algorithm:
define length (lst) if (lst is null) result is 0 else result is 1 + length(cdr of lst)
Remembering that if statements in Lisp produce a value in addition to simply performing a branch, we can translate the pseudo-code into legal Lisp giving us the following:
(defun length (lst) (if (null lst) 0 (+ 1 (length (cdr lst)))))
Lets try another. Suppose we want to create a two-argument function that counts the number of occurrences of the first argument in the second. How can we do this?
You start with the base case. Ask yourself, how many occurrences of the first argument are there in an empty list. The answer, obviously, is zero.
The you take the induction case. If you remove the first element, and then compute the number of occurreces of the first argument in the remainder of the list, then how do we modify this value to determine the number of occurrences in the original list?
The answer, obviously, is to test the head of the list. If it is the element we are seeking, then the answer we want is one larger than the result given by the recursive call, otherwise the result is simply the value given by the recursive call.
If we translate this logic into pseudo-code, we end up with a doublely nested if statement, something like this:
define count (x lst) if (lst is null) then result is 0 else if (x is equal to (car lst)) then result is 1 + count (x cdr(lst)) else result is count(x, cdr(lst))
The translation into legal Lisp is left as an exercise. Note that although there are two recursive calls on count, only one will ever be executed in any situation.
Now what happens if the elements of a list can themselves be lists, and we want to count the occurrences of a value in all lists, regardless of how it is structured? Think first how this changes our previous solution. The base case is still the same -- the number of occurrences in an empty list is still zero. But now what happens in the induction case? It might be the case that the first element in a list is itself a list. If so, we want to recursivly count the values in that list. Otherwise, if the first element is not a list, then we want to do the test as in the original problem. So solving this new problem simply means inserting a new test into our algorithm:
define countAll (x lst) if (lst is null) then result is 0 else if ((car lst) is a list) then result is countAll(x, car lst) + countAll(x, cdr(lst)) else if (x is equal to (car lst)) then result is 1 + countAll (x cdr(lst)) else result is countAll(x, cdr(lst))
Here are some more recursive problems for you to try your hand at: