Recursion is a technique that must be learned as programming in ** Prolog**
depends heavily upon it.

We have already met a recursive definition in section 2.2. Here are some more:

One of my ancestors is one of my parents or one of their ancestors.A string of characters is a single character or a single character followed by a string of characters.

A paragraph is a sentence or a sentence appended to a paragraph.

To decouple a train, uncouple the first carriage and then decouple the rest of the train.

An example recursive program:

talks_about(A,B):-knows(A,B).

talks_about(P,R):-

knows(P,Q),

talks_about(Q,R).

Roughly translated:

You talk about someone either if you know them or you know someone who talks about them

If you look at the AND/OR tree of the search space you can see that

- There is a subtree which is the same shape as the whole tree
reflecting the single recursive call to
**talks_about/2**. - The solution of a given problem depends on being able to stop recursing at some point. Because the leftmost path down the tree is not infinite in length it is reasonable to hope for a solution.

In searching the tree with a number of facts along with the clauses for
** talks_about/2**:

using the goal

If we ask for repeated solutions to this goal, we get, in the order shown:talks_about(X,Y)

X= bill Y= janeX= jane Y= pat

X= jane Y= fred

X= fred Y= bill

X= bill Y= pat

and so on

The search strategy implies that ** Prolog** keep on trying to satisfy
the subgoal ** knows(X,Y)** until there are no more solutions to this.
** Prolog** then finds that, in the second clause for ** talks_about/2**,
it can satisfy
the ** talks_about(X,Y)** goal by first finding a third party
who ** X** knows.
It satisfies ** knows(X,Z)** with ** X=bill**, ** Z=jane** and then recurses looking
for a solution to the goal ** talks_about(jane,Z)**.
It finds the solution by matching against the second ** knows/2** clause.

The above AND/OR tree was formed by taking the top level goal and, for each clause with the same predicate name and arity, creating an OR choice leading to subgoals constructed from the bodies of the matched clauses. For each subgoal in a conjunction of subgoals we create an AND choice.

Note that we have picked up certain relationships holding between
the (logical) variables but we have had to do some renaming to distinguish
between attempts to solve subgoals of the
form ** talks_about(A,B)** recursively.

Mon May 24 20:14:48 BST 1999