recursive-functions


In Scheme, you will often end up writing recursive solutions for your problems. To help you do that, there's a simple pattern on how to think up such solutions. This text tries to explain this to you. You should have some basic understanding of the procedures CONS, CAR and CDR, and the DEFINE form in Scheme to read this text.

The pattern I was talking about consists of two basic questions:

  1. What's the simplest case for your function? That's the base case where it won't recurse.
  2. For a not-so-trivial case, how can you split it up into a smaller problem that looks like what you're doing right now, and some trivial extra work? That's your recursive step.

The second step is usually a bit weird, because we invoke wishful-thinking?. We just assume that the function we're writing right now already exists and belongs to our collection of functions which we may use. The only thing we have to make sure is that we make the problem slightly simpler for this function. We'll notice this in a bit.

A typical application is the recursion over a function (actually, this is so typical that there exist different helper functions which make this easier - MAP, FOLD, etc. - but we'll stick to it as an easy example).

Let's take a very basic function which operates on lists, the LENGTH function. LENGTH gets a list as its argument, and returns the length of the list. For list operations, we have to keep in mind that we have three basic operations: CAR, which returns the head of the list, CDR which returns the list without the first element (the "rest" of the list), and CONS, which prepends an element to a list.

Now applying our steps above:

  1. The trivial case seems to be the empty list. Its length is zero. That's easy enough.
  2. Now for the other case - a nonempty list. Well, invoking wishful-thinking?, we just assume that the function we now are writing already exists. So we have a way to determine the length of a list! But we have to make the problem slightly simpler. A simpler version of the problem would be the length of the rest, the CDR, of the list. This shortens the list by one element, which brings the whole problem closer to the trivial case above. Looks good. But the length of a list is only 1 higher then the length of the rest of the list. That could be written into code!
 ;; This function returns the length of LIS. It's an example for a 
 ;; function which recurses over lists. 
 (define (mylength lis) 
   ;; Trivial case - is the list empty? 
   (if (null? lis) 
       ;; If so, the length is simply 0 
       0 
       ;; If not, the length is 1 longer then the length of the rest of 
       ;; the list: 
       (+ 1 
          (mylength (cdr lis))))) 

Let's have a short look on how that works. Using the substitution-model?, we evaluate this expression:

    (mylength '(1 2 3)) 
 => (+ 1 (mylength '(2 3)))          ;; Recursive step 1 
 => (+ 1 (+ 1 (mylength '(3))))      ;; Recursive step 2 
 => (+ 1 (+ 1 (+ 1 (mylength '())))) ;; Trivial case! 
 => (+ 1 (+ 1 (+ 1 0)))              ;; And now it rolls back 
 => (+ 1 (+ 1 1)) 
 => (+ 1 2) 
 => 3                                ;; Solution 

Now that looks like a good solution.

Let's see what we can learn from this. A good trivial (or base) case for recursions over lists seems to be the empty list. It turns out that this is almost always the best base case. The non-trivial case is almost always solved by applying our current function to the rest of the list, and doing something with the head and the return value of that recursive call.

Now on to a slightly more complicated example. I want to have a function which accepts a list, and returns a list with each element incremented by 1. Back to the two questions:

  1. What is the simplest case? Well, we're recursing over a list, so maybe the base case is again the empty list? Let's see. If we add 1 to every element of the empty list, we get, uh, the empty list. That looks trivial enough! :-)
  2. For a nonempty list, we want to split up the problem again. Since this is list recursion, can we do with the rest of the list? Sure, our own function can do the calculating for the rest. If we have the rest of our list incremented by one each, we only have to prepend (CONS) the head of the list, incremented by one, to get the total list. That looks promising. Let's try:
 ;; Increment each element of LIS by one, and return that as a new 
 ;; list. 
 (define (add-one-to-each lis) 
   ;; Base case again. 
   (if (null? lis) 
       ;; Trivially, this is the empty list: 
       '() 
       ;; Else, we add one to the head of the list, and prepend it to 
       ;; the incremented rest: 
       (cons (+ 1 (car lis)) 
             (add-one-to-each (cdr lis))))) 

Again, we walk through this using the substitution-model?:

    (add-one-to-each '(5 17 23))                        ;; Recursive step 
 => (cons (+ 1 5) (add-one-to-each '(17 23))) 
 => (cons (+ 1 5) (cons (+ 1 17) (add-one-to-each '(23)))) 
 => (cons (+ 1 5) (cons (+ 1 17) (cons (+ 1 23) (add-one-to-each '())))) ;; Base case 
 => (cons (+ 1 5) (cons (+ 1 17) (cons (+ 1 23) '())))  ;; Do the calculation. 
 => (cons (+ 1 5) (cons (+ 1 17) (cons 24 '())))        ;; We drop that extra 
 => (cons (+ 1 5) (cons (+ 1 17) '(24)))                ;; state now. 
 => (cons (+ 1 5) '(18 24)) 
 => '(6 18 24) 

Now that looks like what we wanted to do.

If you look closely, you'll notice that we have two basic patterns now. One turns a list into a single element, the other transforms a list into another list. Let's write down the basic patterns without the specific stuff for our problems:

 ;; A function prototype which turns a list into a single element. 
 ;; This is NOT valid Scheme code! :-) 
 (define (list->element lis) 
   ;; Trivial case - is the list empty? 
   (if (null? lis) 
       ;; If so, return our base value 
       ...base-value... 
       ;; If not, calculate the value of the rest of the list, and do 
       ;; something with it: 
       ...do-something-with (list->element (cdr lis))...)) 

The other one was transforming a list into another list:

 ;; Create a new list where each element is somehow derived from the 
 ;; element at the same position in another list. 
 ;; Again, this is not valid Scheme code! :-) 
 (define (list->list lis) 
   ;; Base case again. 
   (if (null? lis) 
       ;; Usually, this is the empty list, since that is what a list 
       ;; ends with: 
       '() 
       ;; Else, we do something with the head of the list, and prepend 
       ;; it to the transformed rest: 
       (cons (...do-something-with (car lis)...) 
             (list->list (cdr lis))))) 

If you didn't know already, I'll tell you a secret now. Scheme can actually encapsulate those ...do-something-with... things in variables. There's no problem just passing a function to another function as an argument. Now that we know that, we can reformulate the second function somewhat:

 ;; Create a new list where each element is derived from the element at 
 ;; the same position in another list by applying the procedure PROC on 
 ;; it. 
 ;; Now, this IS valid Scheme code! :-) 
 (define (list->list proc lis) 
   ;; Base case again. 
   (if (null? lis) 
       ;; Usually, this is the empty list, since that is what a list 
       ;; ends with: 
       '() 
       ;; Else, we do something with the head of the list, and prepend 
       ;; it to the transformed rest: 
       (cons (proc (car lis)) 
             (list->list proc (cdr lis))))) 

See how we used PROC there as if it was a function? And that's just what's happening here. We also have to pass it on our recursive step back to the function, else we would be passing too few parameters. Let's take a closer look. First, we define a trivial function which adds 1 to its argument:

 (define (add1 x) 
   (+ x 1)) 

Now, if we didn't do anything wrong, we should be able to do

 (list->list add1 '(1 2)) 

Notice how we use the name of ADD1 as the argument, without enclosing it in parenthesis, and thus not calling this function. Let's look how this works in the substitution-model?:

    (list->list add1 '(1 2)) 
 => (cons (add1 1) (list->list add1 '(2))) 
 => (cons (add1 1) (cons (add1 2) (list->list add1 '()))) 
 => (cons (add1 1) (cons (add1 2) '())) 
 => (cons (add1 1) (cons 3 '())) 
 => (cons (add1 1) '(3)) 
 => (cons 2 '(3)) 
 => '(2 3) 

That's what we wanted. Great. :-)

This actually is so common that Scheme defines a function for this. It's called MAP, and works exactly like this:

 > (map add1 '(1 2 3 4 5 6 7 8)) 
 '(2 3 4 5 6 7 8 9) 

Its definition is a bit more complicated then the LIST->LIST we worked up above, but the essence is the same.

I hope you enjoyed reading (and hopefully trying out) this stuff.


category-learning-scheme