13.4 Example of a recursive predicate (Ad)

Introduction

One every-day phenomenon which involves recursivity is that of ancestors and descendants. For example, your father is your ancestor, but so are his father's father and his father's father's father. All of these people are your ancestors, and the relationships can be described elegantly using recursivity.

Defining 'ancestor' recursively

We will not define fully what an ancestor is. This would involve both fathers and mothers, grandfathers and grandmothers, great-grandfathers and great-grandmothers etc. Instead, we will define what a patrilineal ancestor is, i.e., an ancestor who is either the father, the father's father, or the father's father's father, etc.

The recursive definition of a patrilineal ancestor is:

A person A is an ancestor of a person D if:

  1. A is the father of D, or
  2. Some third person F is the father of D, and A is an ancestor of F.

Here, 1. serves as the base case, whereas 2. serves as the recursive part.

Seeing that it works

To see that it works, imagine the following patrilineal ancestry

   Terah
     |
   Abraham
     |
   Isaac
     |
   Jacob
     |
   Judah

Where Terah is an ancestor of all the others, Abraham is an ancestor of Isaac, Jacob, and Judah, etc. etc.

Suppose we want to know whether Terah is an ancestor of Jacob. So we ask: Is Terah, "A", an ancestor of Jacob, "D"?

Well, we can't use part 1. of the definition, since Jacobs's father is Isaac, not Terah. But can we use part 2.?

Some third person F is the father of D. Here, F would be Isaac, and D would be Jacob. Is Terah an ancestor of Isaac?

Again, we can't use part 1. of the definition. But Part 2. yields Abraham (F) is the father of Isaac (D). Is Terah an ancestor of Abraham?

We apply rule 1. Yes, Terah is an ancestor of Abraham, because Terah is Abraham's father. So all of the other rules also succeeded. So Terah is an ancestor of Judah.

All this in Prolog

Consider the following Prolog program. It is available in the AAU directory as: "Ancestors1.plgCG".

father(Terah, Abraham).
father(Abraham, Isaac).
father(Isaac, Jacob).
father(Jacob, Judah).

ancestor(A,D) :- father(A,D).
ancestor(A,D) :- father(F,D), ancestor(A,F).

We see that there is a close correspondence between our definition of what a patrilineal ancestor is and what the predicate "ancestor" is.

Exercise: Try to match each part of the definition above with each part of the Prolog predicate.

The first parameter to the "ancestor/2" predicate is the ancestor, whereas the second parameter is the descendant.

If you have Prolog+CG available, now would be a good time to load the program and test it. For example, you could ask:

?- ancestor(Terah, Abraham).

and the answer would be:

{}

meaning "yes".

If you asked:

?- ancestor(Judah, Abraham).

the answer would be:

no.

since Judah is not an ancestor of Abraham.

Summary

We have seen an example of a recursive predicate. Recursive predicates have a base case not involving the predicate itself. This can either be a fact or a rule. A recursive predicate also has at least one rule which calls the predicate itself. This is the recursive part.

Next

Next, we have a quiz on recursivity and lists


Prev: 13.3 Recursive predicates (Ad)
Up: 13 Recursivity and lists (Ad)
Next: 13.5 Quiz: Recursivity and lists (Ad)