13.2 Recursive definitions (Ad)

Introduction

We have looked at an example of a recursive definition, namely the definition of what a list is. Now it is time to take a look at what it means that a definition is recursive.

What makes a definition 'recursive'?

In order for a definition to be recursive, it needs at least two characteristica:

  1. It needs to define the entity being defined partially in terms of itself. There needs to be an element of self-reference, i.e., the entity being defined must be partially defined by reference to itself.
  2. There must be at least one so-called 'base case' which is not defined in terms of the entity being defined. The base case serves as an 'escape hatch' from the definition so that it does not become circular (more on this below).

Thus, in order for a definition to be recursive, the entity being defined needs to be partially defined in terms of itself, and the definition needs at least one 'base case' not involving the entity being defined.

Application to the definition of lists

Recall that a list is defined as follows. A list is:

  1. Either the empty list, called 'nil',
  2. Or a succession consisting of:
    1. The head of the list, which is an element,
    2. The tail of the list, which is a list.

We see that 1. is the base case, while 2b) provides the self-reference. The base case (a list is an empty list, called 'nil') is not defined in terms of what a list is. The recursive part (the tail of a list is a list) is, by contrast, defined in terms of what a list is.

Why there needs to be a base case

What would happen if there were no base case in the definition of what a list is? The answer is that the definition would not be recursive but circular. We would never be finished describing any particular list:

Suppose we only had rules 2a and 2b. Every list would be infinitely long: When we had specified the first element, we would have to specify what the tail was. But the tail was a list. And a list could only be a head (which was an element) and a tail (which was a list). So we would specify the next element, but be left with the same problem again of saying what the tail was, which was a list. And so on ad infinitum.

So we see that it is precisely the requirement that a recursive definition have at least one base case that saves the definition from being circular. With the base case, the definition is not circular. Without the base case, the definition is always circular, since it defines the element being defined in terms of itself.

Summary

In order for a definition to be recursive, it needs at least these two characteristica:

  1. The entity being defined needs to be defined partially in terms of itself.
  2. There needs to be at least one base case definition which is not defined in terms of the element being defined.

Recursive definitions are not circular precisely because they have at least one base case.

Next

There are other things in Prolog than lists that can be recursive. One of them is predicates. We look at recursive predicates next.


Prev: 13.1 The definition of a list (Ad)
Up: 13 Recursivity and lists (Ad)
Next: 13.3 Recursive predicates (Ad)