Stop condition for recursion in prologue
Here are the facts I have in my knowledge base ( http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/recursion.html (Recursive 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 output something obvious "bob" higher than "george".
I tried to add this rule to solve this problem:
taller(X,Y) :- taller(X,Z),taller(Z,Y).
I need your help to make a stop condition for this recursion, because now I have an error:
| ?- taller(bob,george).
Fatal Error: local Qaru (size: 8192 Kb, environment variable used: LOCALSZ)
thank
source to share
The problem is that your recursive predicate taller/2
is defined as:
taller(X,Y) :-
taller(X,Z),
taller(Z,Y).
As a result, a predicate taller/2
can always lead to two new predicates taller/2
on the call stack, so to speak, and this nesting can go on and on.
The way to deal with this is by separating knowledge from transitive closure . By defining a predicate is_taller/2
that computes the transitive closure of a taller/2
type predicate :
is_taller(X,Y) :-
taller(X,Y).
is_taller(X,Y) :-
taller(X,Z),
is_taller(Z,Y).
Now there is a "guaranteed progression" so to speak, because every time it is called is_taller/2
, it makes a call taller/2
. Since it taller/2
does not have recursion, the number of possible answers is limited. Since this taller/2
is a strict relation to order, we will eventually reach the shortest person, and thus the rollback will be exhausted.
So the complete 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).
source to share