Prolog - generate fibonacci series

Question

I want to write predicate that generates the Fibonacci series for given N.

fibon(6, X) -> X = [0,1,1,2,3,5].

I have a predicate to generate the N-th element of the Fibonacci series:

fib(0, 0).
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.

And I try to write fibon/2, but it doesn't work:

fibon(N, [H|T]) :-
    fib(N, H),
    N1 is N - 1,
    fibon(N1, T).

I solved it like the following:

at_the_end(X, [], [X]).
at_the_end(X, [H|T], [H|T2]) :-
    at_the_end(X, T, T2).

revert([], []).
revert([H|T], Out) :-
    revert(T, Out1),
    at_the_end(H, Out1, Out).

fib(0, 0).
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.

fibon(0, [0]).
fibon(N, [H|T]) :-
    fib(N, H),
    N1 is N - 1,
    fibon(N1, T).

fibonacci(In, Out) :-
    fibon(In, Out1),
    revert(Out1, Out).

Where's your base case for the recursion of fibon/2? What happens if N = 0? or if N < 0? — lurker
You really should have an N > 0 condition in your recursive clause to avoid non-termination issues due to N becoming < 0. Also, your base case probably should be fibon(0, []) since 0 is NOT a Fibonacci number. If you have no Fibonacci numbers (0) then you should have an empty list, yes? — lurker

tas tas · Accepted Answer · 2017-06-12T10:45:34

You can squeeze out a little more speed by making the recursive predicate tail recursive:

fib_seq(0,[0]).                   % <- base case 1
fib_seq(1,[0,1]).                 % <- base case 2
fib_seq(N,Seq) :-
   N > 1,
   fib_seq_(N,SeqR,1,[1,0]),      % <- actual relation (all other cases)
   reverse(SeqR,Seq).             % <- reverse/2 from library(lists)

fib_seq_(N,Seq,N,Seq).
fib_seq_(N,Seq,N0,[B,A|Fs]) :-
   N > N0,
   N1 is N0+1,
   C is A+B,
   fib_seq_(N,Seq,N1,[C,B,A|Fs]). % <- tail recursion

First let's observe that your example query works as expected:

?- fib_seq(6,L).
L = [0, 1, 1, 2, 3, 5, 8] ;
false.

Note that the list doesn't have six elements, as in your example at the beginning of your post, but seven. This is because the predicate starts counting at zero (BTW this is the same behaviour as that of the predicate fibonacci/2 that you added to your post).

For comparison (with fib/2 from @Enigmativity's post) reasons, let's either remove the goal reverse/2 from fib_seq/2 (then you'd get all solutions except N=0 and N=1 in reverse order):

?- time((fib(50000,L),false)).
% 150,001 inferences, 0.396 CPU in 0.396 seconds (100% CPU, 379199 Lips)
false.

?- time((fib_seq(50000,L),false)).
% 150,002 inferences, 0.078 CPU in 0.078 seconds (100% CPU, 1930675 Lips)
false.

Or leave fib_seq/2 as it is and measure fib/2 with an additional goal reverse/2 (then R in the fib/2 solution corresponds to L in the fib_seq/2 solution):

?- time((fib(50000,L),reverse(L,R),false)).
% 200,004 inferences, 0.409 CPU in 0.409 seconds (100% CPU, 488961 Lips)
false.

?- time((fib_seq(50000,L),false)).
% 200,005 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 2267872 Lips)
false.

On a side note, I would urge you to compare your predicate fibonacci/2 with the posted solutions when trying to get bigger lists, say N > 30.

Prolog - generate fibonacci series

4 Answers