# 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