Fibonacci numbers in Prolog

Example for versions Poplog 15.5 (Prolog)

Straightforward recursive implementation is too memory inefficient to be executed in Poplog, so this example shows a more advanced technique — recursion with memoization. An additional predicate `memo(Goal)` is defined so that the first time `Goal` is evaluated, the result of its evaluation is added to facts database, and next time it is questioned, it is not re-evaluated but taken as a known fact.

After this predicate `fib(N,F)` is defined recursively, but each call to `fib` is wrapped in `memo`, so for each value of N `fib(N,F)` is evaluated only once. With such approach printing calculated numbers can be done immediately after their calculation, without extra loop.

``````% fibonacci.pl
:- dynamic(stored/1).

memo(Goal) :-
stored(Goal) -> true;
Goal, assertz(stored(Goal)).

fib(1,1) :- !, write('1, ').
fib(2,1) :- !, write('1, ').
fib(N,F) :-
N1 is N-1, memo(fib(N1,F1)),
N2 is N-2, memo(fib(N2,F2)),
F is F1 + F2,
write(F), write(', ').

% interactive
[-fibonacci].
fib(16,X), write('...'), nl.
``````

Top 10 users: