Tutorial 3

Use of Recursion

The `ancestor` Relation

Suppose we wish to define the ancestor relation ancestor(X,Y) iff X is an ancestor of Y. There are two cases to consider:

Direct ancestors: this can clearly be defined in terms of the parent(X,Y) relation.
Indirect ancestors, i.e. when there is a chain of parents (of length $>1$) linking the two persons in question.

We can implement this in terms of one rule for each case:

Defining ancestor

The first handles direct ancestors.

ancestor(X,Y) :- parent(X,Y).

The second is more complex. One approach might be to use a series of rules of the form

ancestor(X,Z) :-
 parent(X,Y1),
 parent(Y1,Z).

ancestor(X,Z) :-
 parent(X,Y1),
 parent(Y1,Y2),
 parent(Y2,Z).

etc.

but this is clearly incomplete for any finite set of rules.

Recursion

The solution is to use recursion, in which the ancestor relation is defined in terms of itself: For all x and z, x is an ancestor of z if either

x is a parent of z
there is a y such that x is a parent of y and y is an ancestor of z

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

Tracing Execution

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

parent(mike,daniel).
parent(maurice,mike).

| ?- ancestor(maurice,daniel).
   1  1  Call: ancestor(maurice,daniel) ? 
   2  2  Call: parent(maurice,daniel) ? 
   2  2  Fail: parent(maurice,daniel) ? 
   2  2  Call: parent(maurice,_333) ? 
   2  2  Exit: parent(maurice,mike) ? 
   3  2  Call: ancestor(mike,daniel) ? 
   4  3  Call: parent(mike,daniel) ? 
   4  3  Exit: parent(mike,daniel) ? 
   3  2  Exit: ancestor(mike,daniel) ? 
   1  1  Exit: ancestor(maurice,daniel) ?

The `member` Relation

member(X,L) means that X is a member of list L, eg

?- member(b,[a,b,c]). yes
?- member(z,[a,b,c]). no
?- member(X,[a,b,c]). X=a; X=b; X=c

To write a recursive definition, at least two clauses are required: a base clause and a recursive clause.

Base Clause: An item X is a member of a list L if X is the head of L
Recursive Clause: An item X is a member of a list L if X is a member of the tail of L

The `append` Relation

append(X,Y,Z) means that Z is the result of appending X and Y.

?- append([a,b],[c,d],[a,b,c,d]). yes
?- append(  X,  [c,d],[a,b,c,d]). X=[a,b]
?- append(  X,    Y,  [a,b,c,d]). X=[],    Y=[a,b,c,d];
                                  X=[a],   Y=[b,c,d];
                                  X=[a,b], Y=[c,d] etc.

Again two clauses are required for the definition: a base clause and a recursive clause.

Mike Rosner (mros@cs.um.edu.mt)

Last modified: Thu Apr 17 13:15:13 MET DST