17.1. Introduction

This chapter is designed to help you learn about and understand recursion, a powerful programming technique in which a method can call itself to fulfill its purpose.

A recursive definition is one which uses the word or concept being defined in the definition itself. For example, GNU stands for “GNU’s not Unix”.

In some situations, a recursive definition can be an appropriate and concise way to express a concept. Before applying recursion to programming, it is best to practice thinking recursively.

17.1.1. Example: Recursive Data Definition

In general, a recursive data definition specifies how to construct instances of the data. We often call these recursive definitions.

We can define the concept of a list recursively where:

Recursive Definition for a List

A LIST is either a:

  1. number #

  2. or a number comma LIST #, LIST

Notice how we used the term we are defining (LIST) in the definition!

When writing a recursive definition, it is important to have a recursive case and a non-recursive base case. In this example, # is the base case as it is the non-recursive part of the definition. In other words, it is the part of the definition that does not use LIST.

Now we will demonstrate how the following group of numbers satisfies our recursive definition of a LIST:

88, 42, 37

Remember, a LIST can be a # or a #, LIST!

We can demonstrate that 88, 42, 37 is a LIST using the inductively defined recursive data definition by following the definition one step at a time until we reach the base case.

  1. If we look at 88, 42, 37, we see that it does not correspond to the base case. Therefore, we must verify that it matches the recursive case. We see that it starts with a number and a comma. However, to show that this is a LIST, we need to know if 42, 37 is a LIST. Don’t jump ahead! We are limited to the rules given in our recursive definition.

  2. If we look at 42, 37, we see that it also does not correspond to the base case. It is a number, 42, followed by a comma followed by 37. To verify 42, 37 is a LIST, we need to verify that 37 is a LIST.

  3. If we look at 37, we see that it corresponds to our base! Therefore, fits the recursive definition of a LIST.

  4. Since 37 is a LIST, we can also say that 42, 37 is a LIST. Finally, since 42, 37 is a LIST, we can confidently say that 88, 42, 37 is also a list.

As you can see, in order to answer the original problem of whether or not 88, 42, 37 is a list, we used the recursive definition to break it up into smaller sub-problems that get easier to answer. We do not know the overall answer to the original problem until we have answered all of the sub-problems. We’ll explore the idea of problems and sub-problems again in a later section.

We might also represent this with a recursion tree as follows:

88, 42, 37
 /   |    \
88   ,   42, 37
         /  |  \
        42  ,   37
                 |
                37

In general, to create a recursive definition of some concept, we need to establish two things:

  • Base Case: create a non-recursive definition as a “base”.

  • Recursive Case: create a definition in terms of itself, changing it somehow (usually towards the base case).