Recursion

The ancestor/2 problem of exercise 1 discussed above provides a classical example of recursion. Such recursive rules always have two components,

1. the base of the recursion

   ancestor(P, C) :-
      parent(P, C).
   

   and
2. the recursion itself

   ancestor(A, D):-
      parent(A, C),
      ancestor(C, D).
   

The base of the recursion is a non-recursive clause, which, in a computational context, tells the computation when to stop. Here the minimal definition of ancestor is a parent. The recursion crucially involves the predicate calling itself.