Replacing prolog base case with recursive call

Question

I am new to Prolog, started learning it recently using the awesome book Learn Prolog Now!. There is something I don't fully understand and it's really bugging me. One of the exercises questions is

We have the following knowledge base and predicate:

child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  child(X,Z),
                  descend(Z,Y).

What would happen if we change the predicate to the following:

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  descend(Z,Y).

I know that this would cause an infinite recursion on false cases, I can't fully understand why though.

If I understand correctly, in the first case above if a false query is given child(X,Z) would exhaust all its options trying to unify multiple elements to Z then fail, backtrack to the previous X then try option for Z again that would satisfy child(X, Z). (Please correct me if I'm wrong).

I am not sure why the same won't happen though for the second definition of the descend predicate.

Answer 1

Let's take a moment to reduce the snippet you show to a fragment that clearly shows a reason for the nontermination.

The initial fragment is the whole program you posted:

descend(X,Y)  :-  child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  descend(Z,Y).

Now, we insert false/0 at some places. For example:

descend(X,Y)  :-  false, child(X,Y).
descend(X,Y)  :-  descend(X,Z),
                  false,
                  descend(Z,Y).

I am using strikeout text to indicate parts of the program that have no influence on termination. That is, we actually end up with:

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

This fragment alone already causes nontermination. No pure clause you add to this, and nothing that follows the single goal can prevent it! Hence, to make this terminating, you must change this fragment.

See failure-slice for more information.