How to Learn Prolog { day - 2}

Recursion

As is commonly the case in many programming tasks, we often wish to

repeatedly perform some operation either over a whole data-structure, or until

a certain point is reached. The way we typically do this in Prolog is by

recursion. This simply means a program calls itself typically until some final

point is reached. Frequently in Prolog what this means is that we have a first

fact that acts as some stopping condition followed up by some rule(s) that

performs some operation before reinvoking itself.

Recursion is often found to be a hard concept to grasp. For this reason we will

present two detailed examples of how it works.

on_route(rome).
on_route(Place):-
move(Place,Method,NewPlace),
on_route(NewPlace).
move(home,taxi,halifax).
move(halifax,train,gatwick).
move(gatwick,plane,rome).

on_route is a recursive predicate. This program sees if it is possible to travel

to rome from a particular place. The first clause sees if we have already

reached rome, in which case we stop. The second clause sees if there is a

move from the current place, to somewhere new, and then recursive sees if

the NewPlace is on_route to rome. The database of moves that we can make

is on the right.

Let's now consider what happens when we pose the query ?-

on_route(home).

This matches clause two of on_route (it can't match clause

one because home and rome don't unify).

The second on_route clause consists of two subgoals. The first asks whether

you can move from home to some new location i.e. move(home,Method,NewPlace).

This succeeds with

Method = taxi, NewPlace = halifax. This says that yes we can move from

home by taking a taxi to halifax. Next we recursively see if we can find a route

from halifax to rome by doing the same thing again. This is done by executing

the new subgoal on_route(halifax).

The goal on_route(halifax) will fail to unify on clause one, so again we'll use

the recursive clause two and find some new place to go to. Hence we try the

goal move(halifax,Method,NewPlace) this succeeds because we can catch a

train from halifax to gatwick airport. Hence Method=train, NewPlace=gatwick.

As a result we then try the recursive call on_route(gatwick), i.e. we see if there

is a move from gatwick which will get us to rome.

We now try on_route(gatwick), again this only unifies with the second clause.

As a result we try the move clause again this time with Place bound to

gatwick. This query will match the third clause of the move database. The

results in Method=plane, NewPlace=rome. Next we try the recursive goal

on_route(rome). This now matches clause one of on_route. This is just a fact

and succeeds. As a result all the other on_route goals in turn succeed. Thus

finally our first goal ?- on_route(home) succeeds and Prolog responds yes