Prolog/Recursive Rules

This section is about using rules recursively. That is, letting a rule refer to itself. This is one of the most important mechanisms in Prolog, but it can be difficult to work with at first.

Recursive rules

Consider the following program.

 parent(david, john).
 parent(jim, david).
 parent(steve, jim).
 parent(nathan, steve).

 grandparent(A, B) :- parent(A, X), parent(X, B).

It shows a male line in a family tree, and defines with a rule when someone is someone's grandparent (if he's a parent of that person's parent).

What if we wanted to define when someone is an ancestor of someone else? That is, a parent, grandparent, great grandparent and so on. If we would write rules for all these situations we could define ancestor(A,B) for this particular bloodline:

 ancestor(A,B) :- parent(A, B).
 ancestor(A,B) :- parent(A, X), parent(X, B).
 ancestor(A,B) :- parent(A, X), parent(X, Y), parent(Y, B).
 ancestor(A,B) :- parent(A, X), parent(X, Y), parent(Y, Z), parent(Z,B).

Clearly this is not the way to go. It's not elegant, a lot of work and most importantly, it still doesn't define ancestor properly. This may work for a bloodline with four generations, but if we were to add a fifth parent to the program, we'd need a new line for ancestor as well. What we need is a definition for ancestor that works for any line of parents, no matter how long.

To achieve this we need to think about the definition of an ancestor. In the first place, person P is person C's ancestor, if P is C's parent. Furthermore, we can say that person A is person C's ancestor if person A is a parent of an ancestor of C. This doesn't sound very useful, since we use the word ancestor in its own definition, but used together with the first statement, it becomes a complete definition.

For instance, if we were to ask ourselves if Steve is an ancestor of John, we would look at the definitions. Steve is certainly no parent of John, so that doesn't apply. Is Steve the parent of an ancestor of John? Steve is a parent of Jim, so the question becomes, is Jim an ancestor of John? Jim is a parent of David, so is David an ancestor of John? Here we can use the first definition, because David is a parent of John.

In prolog, the definition looks like this:

 ancestor(A, B) :- parent(A, B).
 ancestor(A, B) :- parent(A, X), ancestor(X, B).

The second rule is recursive; it uses ancestor to define ancestor. The first rule is called the stop predicate as it stops the predicate calling itself.

When faced with the query ?- ancestor(steve,john). prolog will first try line one of the definition, but won't be able to unify parent(steve, john) with any line in the database. It will then try the second line and come up with the sub-goals parent(steve, X) and ancestor(X, B). It can unify parent(steve, X) with parent(steve, jim), so prolog is left with the sub-goal ancestor(jim, john). It will continue this until it's left with the subgoal ancestor(david, john) which, using the first line of the definition, is true, because parent(david, john) is true.

Prolog is very comfortable with using recursive rules. It can very easily find all ancestors of John:

 ?- ancestor(X, john).

 X = david ;
 X = jim ;
 X = steve ;
 X = nathan ;
 No

Or all people that Nathan is an ancestor of:

 ?- ancestor(nathan, X).

 X = steve ;
 X = jim ; 
 X = david ;
 X = john ;
 No

Using recursive rules

Using recursive rules is not without its dangers, it can lead to all kinds of loops, which will usually cause stack overflows, meaning prolog has run out of memory. The following guidelines should always be kept in mind when writing recursive rules.

• Start with your stop predicate.

Always put the non-recursive predicate before the recursive predicate. If you start with the recursive predicate prolog will try to search 'deeper' before seeing if it can stop recursing. In the example above, it wouldn't actually make a difference, but your program won't always be so clean and straight-forward.

• Avoid recursion on the left

When writing a recursive rule, if at all possible, put the recursive rule on the right. For instance, use:

a :- b, a. 

instead of

a :- a, b.

This is the same principle as the previous guideline, let prolog evaluate non recursive goals first. If you recurse before you've evaluated the other sub-goals, prolog could either get stuck in infinite recursions, or do a lot of unnecessary work. Sometimes it's necessary to put the recursive element on the left, but don't do it unless you know why you're doing it.

Examples

• A classic example of a recursive function is the factorial function. You can see how this is implemented in the section Math, Functions and Equality. In most programming languages, you might learn recursion by writing a function fact(), which took a positive integer as input, and returned a positive integer. In Prolog, since we usually use predicates instead of functions, we will instead define a predicate fact(X,Y) which is equivalent to the statement, "The factorial of X is Y." Then, to find the factorial of 7, for instance, we would use the query ?- fact(7,X). Prolog will then tell us: X=5040.

• One thing that can easily be defined recursively is a list. In this context we'll consider a list a collection of things (elements) that are placed in some order. To define this recursively, we'll state that a list is a single element, that is followed by a list. To end the recursion we need a second statement, which says that a list is something that consists of an element. Together, these two definitions exactly define anything that is a list.

Lists are actually a very common structure in prolog programs, and they're used in a recursive way. The following chapter explains how.

Exercises

---

prev: Rules next: Variables