# 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.
```

## Comments

]]>blog comments powered by Disqus

]]>