I'm trying to implement the recursive version of the Fibonacci sequence in Prolog. Below is the code:
fib(0,F) :- F is 0.
fib(1,F) :- F is 1.
fib(N,F) :- N > 1,
AA is (N - 1),
BB is (N - 2),
fib(AA,CC),
fib(BB,DD),
RR is (CC + DD),
F == RR,
F is RR.
The problem is that it's not behaving as I logically expect it to. When I use trace to call fib(3,2), I get the following lines:
Call: (7) fib(3, 2) ? creep
Call: (8) 3>1 ? creep
Exit: (8) 3>1 ? creep
Call: (8) _G2569 is 3+ -1 ? creep
Exit: (8) 2 is 3+ -1 ? creep
Call: (8) _G2572 is 3+ -2 ? creep
Exit: (8) 1 is 3+ -2 ? creep
Call: (8) fib(2, _G2573) ? creep
Call: (9) 2>1 ? creep
Exit: (9) 2>1 ? creep
Call: (9) _G2575 is 2+ -1 ? creep
Exit: (9) 1 is 2+ -1 ? creep
Call: (9) _G2578 is 2+ -2 ? creep
Exit: (9) 0 is 2+ -2 ? creep
Call: (9) fib(1, _G2579) ? creep
Call: (10) _G2578 is 1 ? creep
Exit: (10) 1 is 1 ? creep
What catches my attention is the last call, Call: (10), which says "_G2578 is 1 ?", even though I'm calling fib(1, _G2579). My expectation is that it's _G2579 that's going to be changed, but that does not appear to be the case. I need to find out why because I highly suspect that this is why fib(3,2) is returning false instead of true.
The problem, if I'm not wrong, is in
F == R
that check if F (a newly introduced term without a value) is equal to R.
If you change it in
F = R
so unifing F with R (an in redundant following F is R), your fib/2 should work.
But I propose you some semplification.
(1) the terminale case fib(0,F) :- F is 0. is good but you can write it as
fib(0,0).
(2) same semplification for the other terminal case: you can write it as
fib(1,1).
(3) in the general clause, you don't need two different variables F and RR with the same (unified) value; you can use only F in the following way
fib(N,F) :-
N > 1,
AA is (N - 1),
BB is (N - 2),
fib(AA,CC),
fib(BB,DD),
F is (CC + DD).