fibonacci implementation in prolog

Question

I'm trying to make my own implementation of the fibonacci sequence. This is what I have:

fibo2(N, F) :-
    fibo2(0, 1, 0, N, F).

fibo2(N-F, F, N-1, N, F).

fibo2(P, S, C, N, F) :-
    C < N,
    T is S,
    S1 is P + S,
    C1 is C + 1,
    fibo2(T, S1, C1, N, F).

I know there are other implementations but I dont know why this isnt working. When I do a trace with fibo2(3, 2) I think this call should throw true:

fibo2(1, 2, 2, 3, 2) ? creep

But it returns false... Some help would be appreciated

you should include short comments with your code, explaining what each variable is supposed to be, and what is the purpose of each predicate. At least "fibo2(N, F):- % F is N-th Fibonacci number, indexed base 1" should have been there. — Will Ness

m09 m09 · Accepted Answer · 2013-04-22T23:42:14

First, the T is S line serves no purpose. When you do not need to perform arithmetic, prefer the use of standard unification with (=)/2. Here, you could directly call fibo2(S, S1, C1, N, F).

Then, your recursion has no base case. The first clause of fibo2/5 will never be true here.

You certainly meant:

fibo2(P, S, C, N, F) :-
    P is N - F,
    S is F,
    C is N - 1.

Here arithmetic will be performed (when doing unification in the head, arithmetic is not performed, manipulation are entirely symbolic).

I'm not sure what your N and F stand for so I won't comment your code further, but that should fix some problems already.

fibonacci implementation in prolog

1 Answers