Suppose, for instance, that you had a list of numbers and wanted to find their sum. Is there a procedure that adds up the elements of a list in this way?
There's no such built-in procedure, but it's not difficult to define your own. The definition uses a technique called structural recursion.
Is this something different from ordinary recursion?
No, it's just a different way of reducing the given problem to a simpler sub-problem. In our earlier examples, we had a integer parameter and counted down towards zero, or we had a range of values and kept reducing the size of the range on each recursive call. In structural recursion, the approach is to have some data structure, like a list, as the key parameter, and to reduce the size of this structure at each recursive call. In the case of a list, we'll just remove the first element (the car of the list) and supply the rest of the list (its cdr) to the recursive call.
Of course, recursion requires a stopping point. For structural recursion on a list, the natural stopping point is usually the empty list.
So here is how you'd find the sum of the elements of a list of numbers:
(define (sum-of-list ls)
(if (null? ls)
0
(+ (car ls) (sum-of-list (cdr ls)))))
If there are no numbers on the list, the sum is 0. Otherwise, add the
first number on the list to the sum of all the rest. Why is the sum 0 if there are no numbers on the list?
Technically, because zero is the identity element for addition. Practically, because we want the empty list to be the stopping point for the recursion, so we don't want ``the sum of the elements of the empty list'' to contribute anything to the overall total, and the only way to ensure that it won't affect that total is to make it 0.
But you could avoid the empty list by writing this:
(define (sum-of-list ls)
(if (null? (cdr ls))
(car ls)
(+ (car ls) (sum-of-list (cdr ls)))))
Sure, but what's the advantage? You reach the stopping point one step
earlier, it's true, but each step is a little more complicated. And now
whoever invokes your procedure has to make sure that the list he gives it
isn't empty.
Why? What would happen if you gave the empty list to my version of
sum-of-list?
Oh yeah. But it's worth it -- it doesn't make sense to take the sum of the elements of an empty list.> (sum-of-list '()) ERROR: cdr: Wrong type in arg1 ()
Why not? If the sum of the list '(5 5) is 10, and the sum of
the list '(5) is 5, then the sum of the empty list should be
0.
How about a different example?
OK. Here's a recursive procedure that takes any list of numbers and determines how many of them are odd:
(define (how-many-odds ls)
(if (null? ls)
0
(if (odd? (car ls))
(+ 1 (how-many-odds (cdr ls)))
(how-many-odds (cdr ls)))))
An empty list has no odd elements, a list that begins with an odd element
has 1 plus however many there are in the rest of the list, and a list that
begins with an even element has however many odd elements there are in the
rest of the list. Isn't this recursion going to get out of hand? There are two recursive calls in the text of the procedure -- won't the number of recursive calls double when the length of the list is increased by 1?
No, because on any one call to the procedure, either the consequent or the alternative of the if-expression will be evaluated -- never both.
You can write the procedure definition differently, using a let-expression, to make it clear that only a single recursive call will be made:
(define (how-many-odds ls)
(if (null? ls)
0
(let ((odds-in-rest (how-many-odds (cdr ls))))
(if (odd? (car ls))
(+ 1 odds-in-rest)
odds-in-rest))))
Next topic
Previous topic
Table of contents
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/scheme-web/list-recursion.html