Stop condition for recursion in prolog

Question

Here are the facts that I have in my knowledge base (http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/recursion.html (Recursion Exercise 2)):

taller(bob,mike).   % bob is taller than mike
taller(mike,jim).   % mike is taller than jim
taller(jim,george). % jim is taller than george

Now I want to use recursion to deduce something that is obvious "bob" is taller than "george".

I tried to add this rule to solve this:

taller(X,Y) :- taller(X,Z),taller(Z,Y).

I need your help to make a stop condition to this recursion because now I have a stack overflow error:

| ?- taller(bob,george).

Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ)

Thanks

Answer 1

The problem is that your recursive taller/2 predicate is defined as:

taller(X,Y) :-
    taller(X,Z),
    taller(Z,Y).

As a result, a taller/2 predicate can always result in two new taller/2 predicates on the "call stack" so to speak, and this nesting can go on and on.

A way to handle this is separating the knowledge from the transitive closure. By defining an is_taller/2 predicate, that calculates the transitive closure of the taller/2 predicate like:

is_taller(X,Y) :-
    taller(X,Y).
is_taller(X,Y) :-
    taller(X,Z),
    is_taller(Z,Y).

Now there is "guaranteed progression" so to speak, because each time the is_taller/2 is called, it will make a call to taller/2. Since taller/2 has no recursion, the number of possible answers is limited. Since taller/2 is a strict order relation, eventually we will reach the shortest person, and thus the backtracking will get exhausted.

So the full code should be:

taller(bob,mike).   % bob is taller than mike
taller(mike,jim).   % mike is taller than jim
taller(jim,george). % jim is taller than george

is_taller(X,Y) :-
    taller(X,Y).
is_taller(X,Y) :-
    taller(X,Z),
    is_taller(Z,Y).