Recursion is an important technique in many programming languages, especially declarative languages like prolog. It enables elegant and concise ways to describe and solve problems.
Recursion is sometimes perceived as difficult, so we'll use this example to introduce it gently.
% Example 07 - Introducing Recursion
% parent facts
parent(john, jane).
parent(john, james).
parent(sally, jane).
parent(martha, sally).
parent(deirdre, martha).
% grandparent
grandparent(X, Y) :- parent(X, A), parent(A,Y).
% ancestor recursive definition
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,A), ancestor(A,Y).
The first part of the program establishes facts about how six people are related as parents and children. For example, John is the parent of Jane, and Sally is also the parent of Jane. In the code, the names don't start with an uppercase letter because we don't want prolog to treat them as variables.
The following diagram presents this information as a family tree, making it easier to see who is related to whom.
Just to warm up, we can ask basic questions like “who is the parent of Jane?”
?- parent(X, jane).
X = john
X = sally
As expected, prolog tells us both John and Sally are parents of Jane.
Grandparent
Let's turn our attention from parents to grandparents. The program defines a grandparent as follows.
% grandparent
grandparent(X, Y) :- parent(X, A), parent(A,Y).
If a person X is the parent of another person A, and that person A is the parent of someone else Y, then X is the grandparent of Y. That sounds complicated, but is just saying what we know, a grandparent is the parent of a parent.
Let's check it works as expected by asking “who is the grandparent of Jane?”
?- grandparent(X, jane).
X = martha
false
Prolog has found that Martha is indeed the grandparent of Jane. If we run this query, prolog will suggest searching for more solutions. This is because it hasn't completed trying all the combinations for X and A in the definition of grandparent. After we prompt for more solutions, prolog replies with a false because it finds the remaining combinations for X and A don't work.
We might have expected Jane to have the full set of four grandparents, not just Martha. Because they're not described in the database of facts, as far as prolog is concerned, they don't exist. This is called the closed world assumption.
Recursive Definition of Ancestor
We could create similar definitions for great grandparents, great great grandparents, … but that would get boring pretty quickly. Instead, let's see if we can define a general property for all ancestors.
To get started, let's write down what some of these ancestors actually are.
- a grandparent is a parent of a parent,
- a great grandparent is a parent of a grandparent,
- a great great grandparent is a parent of a great grandparent.
We can see a pattern here. Each statement is of the form:
- (ancestor) is a parent of (ancestor one level lower)
This insight isn't a surprise at all, but working out this kind of relationship is key to writing recursive programs in any language, not just prolog.
Our definition of ancestor isn't quite complete. To see why, let's apply the pattern to great grandparent. A great grandparent is a parent of a grandparent. Applying the pattern again, a grandparent is a parent of a parent. We can't apply the pattern again because it looks like we don't have a rule defining parent. Actually, in our example, parents are defined as facts in the prolog database. This means the repeated application of the pattern will eventually terminate.
What we've arrived at is a recursive definition of ancestor. There are two key features of recursive definitions.
- Continuation - a property defined in terms of itself, but reduced by one step. Here, an ancestor is a parent of an ancestor one level lower.
- Termination - a base case which defines the property without referring to itself. Here, the lowest ancestor, a parent, is defined by database facts.
Don't worry if all of this is rather abstract. Recursion is best understood through practice, and we'll do that here, and in later chapters too.
Ancestor/2
Having talked about recursion, let's now look at the definition of ancestor/2 in the example program.
% ancestor recursive definition
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,A), ancestor(A,Y).
The first thing we notice is that ancestor/2 appears to be defined twice. In a previous chapter we saw definitions using the same name for a property but with different arities, specifically sentence/3 and sentence/1. Here both definitions take the same parameters, X and Y, so they both have the same arity. They are both ancestor/2. Is there a clash?
There isn't a clash. Prolog will apply the first rule, and if that's not helpful, it then will try the second rule. This is actually no different to the simple facts we saw earlier, like hairy/1 or tasty/1.
Let's look at the first rule ancestor(X,Y):-parent(X,Y). A parent is the simplest case of being an ancestor, and because parents are defined in the database as facts, this is the termination rule of the recursive definition.
Let's now look at the second rule ancestor(X,Y):-parent(X,A), ancestor(A,Y). This is the pattern we found earlier, and is the continuation rule of the recursive definition. It defines an ancestor in terms of an ancestor one step down. That is, ancestor(A,Y) is one step down on the family tree from ancestor(X,Y) because X is required to be the parent of A.
Before we finish, we should think about the order of the two ancestor/2 rules. In prolog we write the termination rule first because we want prolog to end its search as soon as possible.
We've done a lot of thinking, and the end result is just two short lines of prolog code. That is the right way to do recursion!
Example 1 - Martha & Jane
Let's now talk through our recursive definition ancestor/2 with an example to see how it works in some detail. Let's ask whether Martha is an ancestor of Jane.
The first rule says that if Martha is the parent of Jane, then she is an ancestor of Jane. This rule is not satisfied because the database doesn't tell us that Martha is the parent of Jane.
So we move to the second rule which says that if Martha is the parent of someone A, and A is the ancestor of Jane, then Martha is an ancestor of Jane. Can we find an A that satisfies this rule?
The database tells us that Martha is a parent of A=sally. That's the first part of the rule satisfied. The second part is then asking whether A=sally is the ancestor of Jane. To answer this we apply the first rule again, because it defines ancestor as a parent. The database does indeed tell us that Sally is the parent of Jane, so Sally is an ancestor of Jane. The second rule has been satisfied.
So Martha is indeed an ancestor of Jane.
?- ancestor(martha, jane).
true
The following diagram shows the search tree for this query. We can see how the first rule fails, but the second rule succeeds.
Example 2 - Deirdre & Jane
Let's see how the definition works for another example where the family lineage is a little longer. Let's ask whether Deirdre is an ancestor of Jane.
As usual, we'll apply the first rule. It says Deirdre is an ancestor of Jane if Deirdre is a parent of Jane. This rule is not satisfied because the database doesn't tell us that Deirdre is the parent of Jane.
So we move to the second rule. This says that Deirdre is an ancestor of Jane if Deirdre is a parent of someone A, and A is an ancestor of Jane. Again, can we find an A that satisfies this rule?
The database tells us Deirdre is the parent of A=martha. So the first part of the second rule is satisfied. The second part of the rule is then asking whether A=martha is the ancestor of Jane.
That is the same question we just walked through. We showed that Martha is indeed an ancestor of Jane. So the second part of the rule is satisfied, and therefore Deirdre is an ancestor of Jane.
?- ancestor(deirdre, jane).
true
The key thing to notice is how this problem (Deirdre and Jane) is just the previous problem (Martha and Jane) extended by one parent. This is a feature of scenarios amenable to recursion.
Example 3 - All Jane's Ancestors
If we've defined a problem well enough, we can ask prolog to find answers for us, not just test whether given assertions are true. Let's ask “who are all the ancestors of Jane?”
?- ancestor(X, jane).
X = john
X = sally
X = martha
X = deirdre
Our recursive definition is indeed good enough to generate all the ancestors.
Key Points
- If something isn't provable in a prolog program, it is assumed to be false. This is the closed world assumption.
- Prolog is happy with multiple rules defining a property with the same name and the same arity. Prolog applies the rules in the order they are defined.
- A recursive definition has two key elements, a continuation rule and a termination rule.
- Continuation - a property defined in terms of itself, but with the size of the problem reduced by one step.
- Termination - a simple case which defines the property completely, without referring to the same property.
- In prolog we write the termination rule before the continuation rule because we want prolog to end its search as soon as possible.