Recursion

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:

 
talks_about(X,Y)

 
X= bill 		 Y= jane

X= 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.