CODEWITHSUNDEEP
recursionprolog
interstar
interstar

Reputation: 27186

Prolog : Recursion problem with a calculated end condition

I'm trying to model a set of cog wheels in Prolog. And to query to find if two wheels are connected by a chain of others.

I have a simple recursion :

connected(X,Y) :-   
    engages(X,Y).

connected(X,Y) :-
    engages(X,Z),
    connected(Z,Y).

If I define engages in terms of a hard-wired predicate :

engages(X,Y) :- touches(X,Y).

and 

touches(z1,z2).
touches(z2,z3).
touches(z3,z4).

Then this works.

A test of 

connected(z1,z4).

produces true and 

connected(z1,z5).

produces false.

However, if I replace my touches predicate with a calculation (that the sum of the two radii is roughly the distance between the two centres), then this search goes into what looks like an infinite recursion (stack overflow) when the answer should be false.

Why should this be, given that my "touches" calculation doesn't itself call the "connected" functor? Is it because a touches functor is going to try to match more atoms than the explicit predicates?

This, roughly, is my calculated touches (A and B are the wheels, ARAD and BRAD are their radii, D is distance and approx is an "approximately equals" function.

touches(A,B) :- 
    wheel(A,_,_,ARAD),
    wheel(B,_,_,BRAD),
    distance(A,B,D),
    approx(D,(ARAD+BRAD),2),
    A \== B.

Upvotes: 0

Views: 282

Answers (1)

Fred Foo
Fred Foo

Reputation: 363547

The infinite recursion occurs because the program doesn't check for cycles. Here's what might happen:

  1. The program finds wheels A and B, that touch.
  2. Given B, it looks for a wheel that touches. It finds A.
  3. Goto 1.

You can prevent this from maintaining a "closed set" of wheels already considered in an extra argument to connected:

connected(X,Y) :-
    connected(X,Y,[]).
connected(X,Y,Closed) :-
    touches(X,Y),
    \+ memberchk(Y,Closed).
connected(X,Z,Closed) :-
    touches(X,Y),
    \+ memberchk(Y,Closed),
    connected(Y,Z,[Y|Closed]).

(Exercise for the reader: shorten this.)

Upvotes: 3

Related Questions