Consider the function copy, which creates a list second that is a copy of a list first:
When first is the null list, copy faithfully terminates with the copy also a null list. When first is a one-record list, copy sets second to point to storage allocated for a record and sets the information field value of this record to the value of the information field in first's first record. The recursive call to copy(next(first),&rest) is then an invocation of copy to copy the null list, since next(first) is null in this case. Assuming it performs its task correctly, rest will be null when it returns. The link field of the record pointed to by second is then set to the value of rest (the null pointer), and the initial call to copy terminates correctly.
Similarly, had there been more than one record in first's list, the recursive call to copy would have returned with rest pointing to a correct copy of the list pointed to by next(first). Setlink would correctly place a pointer to that correct copy into the link field of the record pointed to by second, and the initial call would terminate correctly. This verifies that copy is correct in all cases. Again, to copy the null list is easy. To copy a list with at least one record, simply copy that record, copy the rest of the list beyond the first record, and append that copy to the copy of the first record. This is how copy was written!
If you are confronted with a recursive program and want to understand it, approach it in the same way as you would a nonrecursive program. Assume that any functions that are called perform their functions correctly, and then attempt to see what the program itself does. Sometimes this will be apparent, as it was for towers and copy, and sometimes a simulation of the program helps to increase comprehension. Imagine, for example, that you were not told what copy did. It wouldn't have been so easy to find out without simulating some simple cases.
copy(first,psecond)
/* Creates a new list which is a copy
of the list pointed to by first and
whose head is second
*/
listpointer first,*psecond;
{listpointer null, rest,setnull(),avail(),next();
null = setnull();
if(first == null)
*psecond = null;
else
{*psecond = avail();
setinfo(*psecond,first);
copy(next(first),&rest);
setlink(*psecond,rest);
}
}