Fibonacci numbers in 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.