Using Prolog Tabling to Memoize Recursive Fibonacci in SWI-Prolog

When you write a naïve recursive definition of Fibonacci in Prolog, each call recomputes the same sub‑problems many times, leading to exponential run‑time. This makes the program impractical even for modest arguments. The solution is to let the Prolog engine remember previously computed answers so that each distinct sub‑goal is solved only once. In SWI‑Prolog (and several other systems) this mechanism is called tabling or SLG resolution.

Enabling tabling for a predicate

Tabling is activated by a directive that tells the system which predicates should be memoized. For a binary Fibonacci predicate fib/2 the directive is:

:- table fib/2.

Placing this line before the predicate definition instructs SWI‑Prolog to create an internal table for fib/2. Subsequent calls first consult the table; if the answer is already present it is returned immediately, otherwise the call is executed, the result stored, and then returned.
How SLG resolution works
When a tabled predicate is invoked, the engine enters a call phase and a answer phase. During the call phase it checks whether the current sub‑goal already has an entry in the table. If not, it creates a provisional entry and proceeds to compute the answer using the clause body. Each newly discovered answer is added to the table and propagated to any dependent sub‑goals that are waiting. This process guarantees that for a given set of arguments the predicate is evaluated at most once, turning the naïve exponential recursion into linear time proportional to the number of distinct arguments.
Worked example: Fibonacci with tabling
Below is a complete program that defines Fibonacci using the classic recursive clauses and enables tabling.
:- table fib/2.

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.
To compute the 30th Fibonacci number you would query:
?- time(fib(30, X)).
The time/1 predicate reports the execution time; with tabling enabled the call completes in a few milliseconds, whereas the same program without the :- table/1. directive exhibits noticeable slow‑down as the argument grows.
Trade‑offs and verification
Tabling trades extra memory for speed. The system stores one answer per distinct sub‑goal; for fib/2 this means roughly N+1 entries when computing fib(N, _). You can observe this growth with SWI‑Prolog’s statistics:
?- statistics(global_stack, G0),
   statistics(trail_stack, T0),
   fib(30, X),
   statistics(global_stack, G1),
   statistics(trail_stack, T1),
   GlobalIncrease is G1-G0,
   TrailIncrease is T1-T0,
   format('global stack +~d bytes, trail stack +~d bytes~n', [GlobalIncrease, TrailIncrease]).
Increments should be on the order of a few hundred bytes per stored Fibonacci value, confirming that memory use grows linearly with the number of distinct answers.
Another way to see tabling in action is to enable verbose table logging:
?- set_prolog_flag(verbose(table), true),
   fib(5, X).
The console will show messages indicating when a new sub‑goal is inserted into the table and when an existing entry is reused.
Limitations

  
Tabling is not part of the ISO Prolog standard, so code that relies on it may need adjustment when ported to systems that lack the feature.
  
The mechanism assumes logical purity. If a tabled predicate performs side effects such as I/O, assert/1, or retract/1, those effects may occur only the first time the sub‑goal is evaluated, leading to surprising results on later calls. Such predicates should be declared non‑tabled (e.g., :- non_terminal pred/arity.) or isolated from the tabled code.

Actionable closing
If you are writing recursive predicates that repeatedly solve the same sub‑problems—common in dynamic programming, parsing, or graph algorithms—add a :- table/1. directive for those predicates and verify the improvement with time/1 and statistics/2. Keep an eye on memory growth and avoid tabling predicates with side effects. With these steps you can turn an exponential bottleneck into a tractable, linear‑time solution in SWI‑Prolog.