# 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)