Recursion
1.2. Recursion#
Until now, we have encountered two types of logical formulas: facts and rules. There is a special kind of rule which deserves special attention: the rule which defines a relation in terms of itself. This idea of ‘self-reference’, which is called recursion, is also present in most procedural programming languages. Recursion is a bit difficult to grasp, but once you’ve mastered it, you can use it to write very elegant programs, e.g.
IF N=0
THEN FAC:=1
ELSE FAC:=N*FAC(N-1).
is a recursive procedure for calculating the factorial of a given number, written in a Pascal-like procedural language. However, in such languages iteration (looping a pre-specified number of times) is usually preferred over recursion, because it uses memory more efficiently.
In Prolog, however, recursion is the only looping structure1. (This does not necessarily mean that Prolog is always less efficient than a procedural language, because there are ways to write recursive loops that are just as efficient as iterative loops, as we will see in Section 3.6.) Perhaps the easiest way to think about recursion is the following: an arbitrarily large chain is described by describing how one link in the chain is connected to the next. For instance, let us define the relation of reachability in our underground example, where a station is reachable from another station if they are connected by one or more lines. We could define it by the following 20 ground facts:
reachable(bond_street,charing_cross).
reachable(bond_street,green_park).
reachable(bond_street,leicester_square).
reachable(bond_street,oxford_circus).
reachable(bond_street,piccadilly_circus).
reachable(bond_street,tottenham_court_road).
reachable(green_park,charing_cross).
reachable(green_park,leicester_square).
reachable(green_park,oxford_circus).
reachable(green_park,piccadilly_circus).
reachable(green_park,tottenham_court_road).
reachable(leicester_square,charing_cross).
reachable(oxford_circus,charing_cross).
reachable(oxford_circus,leicester_square).
reachable(oxford_circus,piccadilly_circus).
reachable(oxford_circus,tottenham_court_road).
reachable(piccadilly_circus,charing_cross).
reachable(piccadilly_circus,leicester_square).
reachable(tottenham_court_road,charing_cross).
reachable(tottenham_court_road,leicester_square).
Since any station is reachable from any other station by a route with at most two intermediate stations, we could instead use the following (non-recursive) definition:
reachable(X,Y):-connected(X,Y,L).
reachable(X,Y):-connected(X,Z,L1),connected(Z,Y,L2).
reachable(X,Y):-connected(X,Z1,L1),connected(Z1,Z2,L2),
connected(Z2,Y,L3).
Of course, if we were to define the reachability relation for the entire London underground, we would need a lot more, longer and longer rules. Recursion is a much more convenient and natural way to define such chains of arbitrary length:
reachable(X,Y):-connected(X,Y,_L).
reachable(X,Y):-connected(X,Z,L),reachable(Z,Y).
The reading of the second rule is as follows: ‘Y is reachable from X if Z is directly connected to X via line L, and Y is reachable from Z’.
Figure 1.3 A proof tree for the query ?-reachable(bond_street,W).#
We can now use this recursive definition to prove that Leicester Square is reachable from Bond Street (Figure 1.3). However, just as there are several routes from Bond Street to Leicester Square, there are several alternative proofs of the fact that Leicester Square is reachable from Bond Street. An alternative proof is given in Figure 1.4. The difference between these two proofs is that in the first proof we use the fact
connected(oxford_circus,tottenham_court_road,central).
while in the second proof we use
connected(oxford_circus,piccadilly_circus,bakerloo).
There is no reason to prefer one over the other, but since Prolog searches the given formulas top-down, it will find the first proof before the second. Thus, the order of the clauses determines the order in which answers are found. As we will see in Chapter 3, it sometimes even determines whether any answers are found at all.
Figure 1.4 Alternative proof tree for the query ?-reachable(bond_street,W).#
Exercise 1.3 #
Give a third proof tree for the answer { W → leicester_square }, and change the order of the facts for connectedness, such that this proof tree is constructed first.
In other words, Prolog’s query-answering process is a search process, in which the answer depends on all the choices made earlier. A important point is that some of these choices may lead to a dead-end later. For example, if the recursive formula for the reachability relation had been tried before the non-recursive one, the bottom part of Figure 1.3 would have been as in Figure 1.5. This proof tree cannot be completed, because there are no answers to the query ?-reachable(charing_cross,W), as can easily be checked.
Prolog has to recover from this failure by climbing up the tree, reconsidering previous choices. This search process, which is called backtracking, will be detailed in Chapter 5.
Figure 1.5 A failing proof tree.#
- 1
If we take Prolog’s procedural behaviour into account, there are alternatives to recursive loops such as the so-called failure-driven loop (see Exercise 7.5).