Prolog: Part 3 - Recursion
Why is recursion so important?
Recursion is a key concept in logic programming because is all about logical reasoning, pattern matching, and logical inference. Prolog programs solve problems through recursive principles, where programmers specify what needs to be solved, rather than how to solve it.
In other words, by specifying the base cases and recursive cases, recursive predicates can define relationships that hold for a base case and are extended to subsequent cases through recursive calls.
Example
Suppose we have a knowledge base with these facts:
child(priya,aisha).
child(aisha,sadie).
This knowledge base can be interpreted as: "aisha is a child of priya, and sadie is a child of aisha".
Suppose we wanted to define the descendant relation; that is, the relation of being a child of, or a child of a child of, or a child of a child of a child of, and so on.
We could add the following two non-recursive rules to the knowledge base:
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
child(Z,Y).
These definitions work up to a point, but they are limited. They only define the concept of descendent-of for two generations or less. Suppose we want to expand our facts like this:
child(belle,priya).
child(priya,aisha).
child(aisha,sadie).
child(sadie,lily).
Now our two rules are inadequate. For example, if we pose the queries:
?- descend(belle,sadie).
or
?- descend(priya,lily).
we get the answer "No", which is not what we want.
Recursive Predicates
Consider the following recursive rules:
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
Why Does This Work?
- The interpretation of the base clause is: if Y is a child of Y, then Y is a descendant of X.
- The interpretation of the recursive clause is: if Z is a child of X, and Y is a descendant of Z, then Y is a descendant of X.
Let's take a closer look at the recursive predicate by stepping through an example.
Suppose we pose the query:
descend(belle,sadie)
Remember that Prolog performs a depth-first search strategy. This allows Prolog to navigate a problem space by continuously breaking it down into smaller sub-problems until a solution is found. When Prolog reaches the end of a particular path in the search tree, it uses a backtracking mechanism to explore alternative solutions. Note that backtracking can result in multiple solutions.
Prolog first tries the first rule. The variable X in the head of the rule is unified with belle and Y with sadie and the next goal Prolog tries to prove is
child(belle,sadie)
This attempt fails because the knowledge base neither contains the fact child(belle,sadie) nor any rules that would allow to infer it. Prolog backtracks and looks for an alternative way of proving descend(belle,sadie). It finds the second rule in the knowledge base and now has the following subgoals:
child(belle,_633),
descend(_633,sadie).
Prolog takes the first subgoal and tries to unify it. It finds the fact child(belle,priya) and the variable _633 gets instantiated to priya. Since the first subgoal is satisfied, Prolog moves to the second subgoal. It has to prove
descend(priya,sadie)
This is the recursive call of the predicate descend/2. As before, Prolog starts with the first rule, but fails, because the goal
child(priya,sadie)
cannot be proved. Backtracking, Prolog finds that there is a second possibility to be checked for descend(priya,sadie) due to the second rule, which again gives Prolog two new subgoals:
child(priya,_1785),
descend(_1785,sadie).
The first subgoal can be unified with the fact child(priya,aisha) of the knowledge base, so that the variable _1785 is instantiated with aisha. Next Prolog tries to prove
descend(aisha,sadie).
This is the second recursive call of predicate descend/2. As before, it tries the first rule first, obtaining the following new goal:
child(aisha,sadie)
This time Prolog succeeds, since child(aisha,sadie) is a fact.
Prolog has found a proof for the goal descend(aisha,sadie) - the second recursive call. But this means that child(priya,sadie) - the first recursive call - is also true, which means that our original query descend(belle,sadie) is true as well.