Prolog (3)

< 1 2 3 4 >

Recursion in Prolog:
Recursion is a technique which allows the user to implement data structures like trees where various number of steps in necessary to answer the question. Recursion uses multiple cases, including a base case, though the number of cases is usually only two.

For example the relation "ancestor", which finds the ancestors of a variable X. The ancestor can be an immediate parent of X, otherwise the parent of a parent of X needs to be checked and so on.

ancestor(X, Y) :- parent(X, Y).                
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

How does Prolog answer questions?
A question is normally a sequence of one or more goals. To satisfy a goal means to demonstrate that it logically follows from a set of already defines rules and facts. In case the question contains variables, Prolog will also find possible values of these variables to make the question true (if any exist).

Prolog interprets all the given facts and rules as a set of axioms and user's question as a conjectured theorem. Then it attempts to solve the theorem thus to show that it logically follows from the axioms. Prolog follows the chain of rules in reverse order. So given a theorem it checks if the head of the computation can be replaced with any other rules which consequently become new goals. If the given theorem is true the chain should eventually terminate as soon as the goals can be replaced with already established facts. Any unsuccessful attempt to carry out a substitution triggers a backtrack and the attempt of an alternative clause.

Here is an example of how Prolog can be used to solve a very famous recursive puzzle: the towers of Hanoi:

hanoi(N) :- move(N, left, centre, right).
move(0, _, _, _) :- !.
move(N, A, B, C) :- M is N-1, move(M, A, C, B), inform(A, B), move(M, C, B, A).
inform(X, Y) :- write([move, a, disc, from, the, X, pole, to, the, Y, pole]),nl.

< 1 2 3 4 >