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 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
parent(john,paul). /* paul is john's parent */
parent(paul,tom). /* tom is paul's parent */
parent(tom,mary). /* mary is tom's parent */
ancestor(X,Y):- parent(X,Y). /* someone is your ancestor if there are your parent */
The first clause of ancestor looks to see if there exists a clause that could match the goal parent(john,tom). This fails to match, as a result we try the second clause of ancestor. We now pose the query parent(john,Z). This results in us choosing clause one of parent and binding Z=paul. As a result, we now pose the recursive query ancestor(paul,tom). Applying the ancestor rule again, we first try the first clause. This means we check for parent(paul,tom). which successfully matches the second clause of parent. As a result the goal ancestor(paul,tom) succeeds. This in turn leads to the goal ancestor(john,tom) succeeding and Prolog responding yes
Exercise 8 - Recursion Exercise
Which of the following programs uses recursion.
Write a recursive program that will determine that Bob's height is greater than George's.
Bob is taller than Mike.
Mike is taller than Jim
Jim is taller than George
A one way road links 6 towns. Write a program that can work out if you can travel on that road. For example. Here are two sample program behaviours.
Return to the Introduction Menu