Swipe to navigate through the chapters of this book
This chapter introduces induction and recursion, which are omnipresent in computer science. The simplest context in which they arise is in the domain of the positive integers, and that is where we begin. We explain induction as a method for proving facts about the positive integers, and recursion as a method for defining functions on the same domain. We will also describe two different methods for evaluating such functions.
From this familiar terrain, the basic concepts of recursion and induction can be extended to structures, processes and procedures of many kinds, not only numerical ones. Particularly useful for computer scientists are the forms known as structural induction and recursion, and we give them special attention. We will look at structural recursion as a way of defining sets, structural induction as a way of proving things about those sets, and then structural recursion once more as a way of defining functions with recursively defined domains. At this last point, special care is needed, as the definitions of such functions succeed only when a special condition of unique decomposability is satisfied which, happily, is the case in many computer science applications.
The broadest and most powerful kind of induction/recursion may be formulated for sets of any kind, provided they are equipped with a relation that is well founded, in a sense we explain. All other kinds may be seen as special cases of that one. In a final section, we look at the notion of a recursive program and see how the ideas that we have developed in the chapter are manifested there.
Please log in to get access to this content
Induction and recursion on the positive integers. There are plenty of texts, although most tend to neglect recursive definition in favour of inductive proof. Here are three among them:
Hein JL (2005) Discrete structures, logic and computability, 2nd edn. Jones and Bartlett, New York, chapter 4.4
Schumacher C (2001) Chapter zero: fundamental notions of abstract mathematics. Pearson, Boston, chapter 3
Velleman DJ (2006) How to prove it: a structured approach, 2nd edn. Cambridge University Press, New York, chapter 6
Well-founded induction and recursion. Introductory accounts tend to be written for students of mathematics rather than computer science and, again, tend to neglect recursive definition. Two texts accessible to computer science students are:
Lipschutz S (1998) Set theory and related topics, Schaum’s outline series. McGraw Hill, New York, chapters 8–9
Halmos PR (2001) Naive set theory, New edn. Springer, New York, chapters 17–19
Structural induction and recursion. It is rather difficult to find introductory presentations. One of the purposes of the present chapter has been to fill the gap!
- Recycling Outputs as Inputs: Induction and Recursion
- Springer London
- Sequence number
- Chapter number