We will now present a series of functions to further illustrate recursive programs. The functions
1. Determine the length of a list
2. Create a list that is a copy of another list
3. Count checkerboard placements
4. Generate all permutations of n integers and process each one. (This is applied to the stable marriage problem.)
In addition to providing repetition so that you can become more familiar with and understand recursion better, the examples provide a background to show how local and global variables and parameters are treated in recursive programs and why recursive solutions are not always the best. A list may be thought of as being either a null list or as one record followed by another list (the link field of the record plays the role of the head of this other list). This is nothing but a way to define a list recursively. Consider the recursive function defined by
This function returns the length of the list, listname. To verify that this is correct we must check
1. The null list. It returns with length = 0.
2. A one-record list followed by another list. It returns length = 1 + the length of the list after the first record.
It is correct, since its value is correct for each case. Of course it is correct?/FONT>after all, the length of a null list is zero, and the length of a list with at least one record is 1 for the record, plus the length of the rest of the list beyond the first record ! This was how length was written in the first place.
length(listname)
/* Returns the number of records
in the list pointed to by listname.
*/
listpointer listname;
{listpointer setnull(),next();
if(listname == setnull())
return(0);
else
return(1 + length(next(listname)));
}