Induction and Recursion

The main purpose of this chapter is to introduce recursion. Recursion is a simple yet powerful idea that can be enormously useful in developing algorithms for solving complex problems. This is especially true if an algorithm is to be implemented in Lisp or a related programming language such as Scheme. We will also introduce the method of proof by induction, a technique closely related to recursion. In addition to being one of the standard proof techniques in mathematics, induction is a useful technique for verifying the correctness of algorithms.