Almost any non-trivial prolog program involves recursive predicates - predicates that call themselves. The basic idea should be familiar from recursive function definitions in functional languages. However, as Prolog is not based on function application, the way recursive predicates are used and written is slightly different.
Suppose we want to write a Prolog procedure to determine whether someone is an ancestor of someone else. This has a natural recursive definition. X is Y's ancestor if X is Y's parent OR Z is Y's parent and X is Z's ancestor. This can be written as follows:
ancestor(Person, Ancestor) :- % Rule 1: Base case
parent(Person, Ancestor).
ancestor(Person, Ancestor) :- % Rule 2: Recursive case
parent(Person, Parent),
ancestor(Parent, Ancestor).
Note how the base case of the recursive definition is a separate rule, preceding the recursive case. All recursive predicates must have a base case, otherwise they would either fail or recurse for ever.
Consider what happens if we also have the following facts:
parent(alison, david). % fact 1 parent(alison, kathleen). % fact 2 parent(david, harold). % fact 3 parent(david, ida). parent(kathleen, john). % fact 5
and we ask:
?- ancestor(alison, harold).
Prolog will match the query against rule 1, and try to prove parent(alison, harold). This will fail, so Prolog will backtrack and try the second rule. parent(alison, Parent) first succeeds with Parent = david, so Prolog tries to prove ancestor(david, harold). Matching this new term against the head of the first rule, and sucessfully proving parent(david, harold), the whole query succeeds.
If we try to prove ancestor(alison, john) things get a bit more complex as Prolog has to backtrack. parent(alison, david) is no good, as it won't be able to prove ancestor(david, john). It will have to backtrack, finding parent(alison, kathleen), and proving ancestor(kathleen, john).
It is probably wise not to think TOO hard about what happens when Prolog backtracks through complex recursive predicate definitions. They can often be easily understood declaratively, and you should soon get a feel for what will happen, without having to trace everything out in detail. Suppose for example we give the following query, and force backtracking (e.g., by typing a semicolon).
?- ancestor(alison, Ancestor). Ancestor = david ; Ancestor = kathleen ; Ancestor = harold ; Ancestor = ida ; Ancestor = john ; no
Prolog first finds all the facts that match with the subgoal of the base case (Ancestor = david; kathleen). Then finds all david's ancestors (harold; ida), then all kathleen's ancestors (john). If we added a fact parent(harold, fred) then Ancestor = fred would be given after Ancestor = ida, as Prolog tried to find all harold's ancestors.