Common Themes: Self-Definition and Basis-Induction As you study this chapter, you should be alert to two themes that run through the various concepts. The first is self-definition, in which a concept is defined, or built, in terms of itself. For example, we mentioned that a list can be defined as being empty or as being an element followed by a list. The second theme is basis-induction. Recursive functions usually have some sort of test for a “basis” case where no recursive calls are made and an “inductive” case where one or more recursive calls are made. Inductive proofs are well known to consist of a basis and an inductive step, as do inductive definitions.

This basis- induction pairing is so important that these words are highlighted in the text to introduce each occurrence of a basis case or an inductive step. There is no paradox or circularity involved in properly used self-definition, because the self-defined subparts are always “smaller” than the object being defined. Further, after a finite number of steps to smaller parts, we arrive at the basis case, at which the self-definition ends. For example, a list L is built from an element and a list that is one element shorter than L.

When we reach a list with zero elements, we have the basis case of the definition of a list: “The empty list is a list.” As another example, if a recursive function works, the arguments of the call must, in some sense, be “smaller” than the arguments of the calling copy of the function. Moreover, after some number of recursive calls, we must get to arguments that are so “small” that the function does not make any more recursive calls.