First, two assumptions:

• the actual code you want to write is the following, with the corresponding dots:

  friends(mia,ellen).
  friends(mia,lucy).
  friends(X,Y) :- 
     friends(X,Z),
     friends(Z,Y).
  
        
  
          
          
          
        
  
      

• The presence of friends: friends of friends are also my friends (I would prefer to model friendship as distance: "A is close to B" and "B is close to C" does not mean that "A is near C"), repeating the answer is a correct definition of what you want to simulate.

Now let's see why we are moving to infinite recursion.

Step by step

So what happens when we ask friends(mia,X)

:?

• The first suggestion gives Y=ellen
  
  (you are asking for more solutions)
• The second suggestion gives Y=lucy
  
  (you are asking for more solutions again)
• Stack overflow!

Detailed description of the third sentence:

• I want to know if friends(mia,Y)
  
  for some variable exists Y
  
  .

• Is there a variable Z
  
  such that it friends(mia,Z)
  
  gets executed?

  Note that apart from renaming from Y
  
  to Z
  
  , we are asking the same question as step 1 above? It smells like endless recursion , but let's see ...

• We try the first two sentences friends
  
  , but then we fail because we don't, friends(ellen,Y)
  
  and friends(lucy,Y)
  
  so ...
• We call the third clause to find if a transitive friendship exists and we go back to step 1 without reaching further infinite recursions.

This problem is similar to infinite left recursion in context-free grammars.

Fix

They have two predicates:

• known_friends/2
  
  which gives a direct relationship.

• friends/2
  
  which also encodes transitivity

  known_friends(mia,ellen).
  known_friends(mia,lucy).
  
  friends(X,Y) :- known_friends(X,Y).
  friends(X,Y) :- known_friends(X,Z), friends(Z,Y).
  
        
  
          
          
          
        
  
      

Now, when we ask friends(mia,X)

, friends/2

gives the same answer as the two sentences known_friends/2

, but finds no answer for a transitive sentence: the difference is what known_friends

will make little progress, namely find a known friend mia

(no recursion) and try to find (recursively) if this one is a friend of some people.

Friends of friends

If we add known_friends(ellen, bishop)

^{: -)} that friends

also will Y=bishop

because:

• known_friends(mia,ellen)
  
  is executed, and
• friends(ellen,bishop)
  
  found recursively.

roundness

If you add circular dependencies in the friendship graph (c known_friends

), you get an infinite traversal of that graph with friends

. Before you can fix this, you must consider the following questions:

• Does it work friends(X,Y) <=> friends(Y,X)
  
  for everyone (X,Y)
  
  ?
• What about friends(X,X)
  
  , for everyone X
  
  ?

Then, when you evaluate friends

, you should keep a set of all the people seen to detect when you go through known_friends

, taking the above properties into account. It shouldn't be too hard if you want to try it.