Is this left recursion in Prolog?

Question

I'm using swipl 5.10.2. I started today learning Prolog for my AI course. I've started with a pretty straight forward example:

father(giovanni,maria).
brother(paolo,pietro).

grandpa(X,Y) :-
        father(X,Z),
        father(Z,Y).
grandpa(X,Y) :-
        father(X,Z),
        mother(Z,Y).

mother(maria,paolo).
mother(I,J) :-
        mother(I,K),
        brother(K,J).

Not a big deal, if I try this goal grandpa(giovanni,pietro), it work and it gives me true. Then I want to spicy up the challenge and I modified the code like this:

father(giovanni,maria).
brother(paolo,pietro).

grandpa(X,Y,Z) :-
        father(X,Z),
        father(Z,Y).
grandpa(X,Y,Z) :-
        father(X,Z),
        mother(Z,Y).

mother(maria,paolo).
mother(I,J) :-
        mother(I,K),
        brother(K,J).

because I wanted to know the middle-man but when I run it here's what happens:

?- grandpa(giovanni,pietro,M).
M = maria ;
ERROR: Out of local stack

That's because, imho, there's a left recursion in mother, the tree keeps expanding without finding closure.

Then I wrote this:

father(giovanni,maria).
brother(paolo,pietro).
mother(maria,paolo).

grandpa(X,Y,Z) :-
        father(X,Z),
        father(Z,Y).
grandpa(X,Y,Z) :-
        father(X,Z),
        mother(Z,Y).

mother(I,J) :-
        brother(K,J),
        mother(I,K).

This is the output:

?- grandpa(giovanni,pietro,M).
M = maria ;
false.

It is right. So is it just a left recursion problem or am I missing something about swipl behaviour? And when I have a "ERROR: Out of local stack", is it always a recursion problem?

Jeremiah Willcock Jeremiah Willcock · Accepted Answer · 2011-02-25T20:22:44

I believe the Out of local stack error is almost always (or always) from recursions that are too deep; in simple programs, those recursions are likely to be infinite. The problem in your code is indeed the left recursion issue; trying to solve mother(anything, B) will try to solve mother(anything, B1), mother(anything, B2), and so on until you run out of stack space.

Is this left recursion in Prolog?

1 Answers