Why my predicate in Prolog Fib/2 always says "out of local stack"?

Question

I wrote a predicate fib/2 to calculate the Fibonacci numbers in Prolog. Though it works, it always says "out of local stack" and the error looks like:

?- fib(10, F).
F = 55 ;
ERROR: Out of local stack

my predicate is below:

fib(0, 0).
fib(1, 1).
fib(N, NF) :-
    A is N - 1, 
    B is N - 2,
    fib(A, AF), 
    fib(B, BF),
    NF is AF + BF.

Anyone knows why this is and how to fix it to get the following stuff::

% or the search might stop immediately, without pressing space.
?- fib2(10, F).
F = 55 ;
false. 

Thanks in advance!

Answer 1

The out of local stack error means that the program used too much memory and exceeded the allocated space; this occurs often when the program falls in an infinite loop. In your case, here is the trace:

[trace] 2 ?- fib(2,M).
   Call: (6) fib(2, _G671) ? creep
^  Call: (7) _G746 is 2+ -1 ? creep
^  Exit: (7) 1 is 2+ -1 ? creep
^  Call: (7) _G749 is 2+ -2 ? creep
^  Exit: (7) 0 is 2+ -2 ? creep
   Call: (7) fib(1, _G747) ? creep
   Exit: (7) fib(1, 1) ? creep
   Call: (7) fib(0, _G747) ? creep
   Exit: (7) fib(0, 0) ? creep
^  Call: (7) _G671 is 1+0 ? creep
^  Exit: (7) 1 is 1+0 ? creep
   Exit: (6) fib(2, 1) ? creep
M = 1 ;
   Redo: (7) fib(0, _G747) ? creep
^  Call: (8) _G752 is 0+ -1 ? creep
^  Exit: (8) -1 is 0+ -1 ? creep
^  Call: (8) _G755 is 0+ -2 ? creep
^  Exit: (8) -2 is 0+ -2 ? creep
   Call: (8) fib(-1, _G753) ? creep
^  Call: (9) _G758 is -1+ -1 ? creep
^  Exit: (9) -2 is -1+ -1 ? creep
^  Call: (9) _G761 is -1+ -2 ? creep
^  Exit: (9) -3 is -1+ -2 ? creep
   Call: (9) fib(-2, _G759) ? creep
^  Call: (10) _G764 is -2+ -1 ? creep
^  Exit: (10) -3 is -2+ -1 ? creep
...

as you can see, after finding that the 2nd fibonacci is 1 (by your definition) you ask for a second solution; since you haven't specified that the third clause may only be used when N>1 prolog tries to find the second solution by calculating fib(-1), fib(-2), fib(-3) etc.

to fix it, you have to add N>1 or a similar rule to the third clause