We can avoid this by using memo-functions:
fib( N, F ) :-
memo_fib( N, F ).
fib( 0, 1 ).
fib( 1, 1 ).
fib( N, F ) :-
N1 is N - 1,
N2 is N - 2,
fib( N1, F1 ),
fib( N2, F2 ),
F is F1 + F2,
asserta( memo_fib(N,F) ).
Clauses for memo_fib get generated as the program runs, and avoid
recalculating already-known results.