Prolog; try to make fibonacci more effective?

Question

This logic programming is really making a lap dance on my imperative programming skills. This is homework, so please just don't drop me the answer. This is what I have:

fibo(N,1) :-
   N < 2,
   !. 
fibo(N,R) :-
   N1 is N-1,
   N2 is N-2,
   fibo(N1,R1),
   fibo(N2,R2),
   R is R1+R2.

I'm suppose to make another function that looks like this; fib(N,Value,LastValue). N is the n'th number, and value is the return value. I don't understand how I can rewrite this using accumulation. And since it counts backwards I don't see how it can "know" a last value before it calculates anything. :s Any input is appreciated.

Answer 1

I could post here the solution, but since that this is homework, it would be counter-productive. Instead, here's a lead:

The problem with the version of Fibonacci that you listed is that it is inefficient. Each call to fibo/2 causes another two calls, but some of these calls calculate the values of the same Fibonacci numbers. For example, in pseudo-code:

(a) fibo(4) -> fibo(3), fibo(2)
(b) fibo(3) -> fibo(2), fibo(1)
(c) fibo(2) -> fibo(1), fibo(0) % called from (a)
(d) fibo(2) -> fibo(1), fibo(0) % called from (b), redundant

To overcome this deficiency, you were asked to rephrase Fibonacci in terms of returning not just the last value, but the last two values, so that each call to fib/3 will cause only a single recursive call (hence calculate the Fibonacci series in linear time). You'll need to change the base cases to:

fib(1,1,0).
fib(2,1,1).

I'll leave the recursive case to you.

---

For the impatient

Here is the recursive case as well:

fib(N, Val, Last) :-
  N > 2,
  N1 is N - 1,
  fib(N1, Last, Last1), % single call with two output arguments, 
                        % instead of two calls with one output argument
  Val is Last + Last1.

Answer 2

See the related discussion:

Generalizing Fibonacci sequence with SICStus Prolog

and consider ony's very good solution using finite domain constraints from there.