13.2 Recursive definitions (Ad)
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:
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:
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.
In order for a definition to be recursive, it needs at least these two characteristica:
Recursive definitions are not circular precisely because they have at least one base case.
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)