% fib(N,F) holds when F is the n-th Fibonacci number.
% The first and second Fibonacci numbers are 0 and 1.
% The nth Fibonacci number (n>2) is the sum of the previous two.

fib(0,0). % start counting at zero
fib(1,1).
fib(N,F) :- N>1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+F2.

% With pairs
fibP(0,0). % Special case
fibP(N,F) :- N>0, fibP(N,F,_).
fibP(1,1,0).
fibP(N,F3,F2) :- N>1, N1 is N-1, fibP(N1,F2,F1), F3 is F2+F1.

% Tail Recursive Version
fibA(0,0). % Special case
fibA(N,F) :- N>0, fibA(N,0,1,F).
fibA(1,_,F,F).
fibA(N,A1,A2,F) :- N1 is N-1, A3 is A1+A2, fibA(N1,A2,A3,F).
