HomeContents: |
## 13.2 Recursive definitions (Ad)## IntroductionWe 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: - 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. - 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 listsRecall that a list is defined as follows. A list is: *Either*the empty list, called 'nil',*Or*a succession consisting of:- The
*head*of the list, which is an*element*, - The
*tail*of the list, which is a*list*.
- The
We see that 1. is the ## Why there needs to be a base caseWhat 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 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 ## SummaryIn order for a definition to be recursive, it needs at least these two characteristica: - The entity being defined needs to be defined partially in terms of itself.
- 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. ## NextThere 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) |