Using Prolog Tabling to Turn Exponential Recursion into Linear Time

The Problem: Exponential Recursion in Plain Prolog

When a predicate calls itself recursively without memoization, each distinct subgoal is evaluated from scratch every time it appears. For the Fibonacci definition this leads to an exponential number of calls.

Naive Fibonacci

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.

Calling fib(30,X) triggers roughly 2^30 recursive calls.

How Tabling Changes the Evaluation

Tabling (SLG resolution) stores the answer set for each distinct subgoal the first time it is solved. Subsequent identical calls fetch the cached answers instead of re‑deriving them.

Declaring a tabled predicate

:- 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.

The first call to fib(30,_) builds a table with entries for fib(0,_) … fib(30,_). Each entry is filled once, giving linear O(N) work.

Worked Example: Measuring the Difference

Create a file fib.pl containing both versions, guarded by a module or separate predicates.

:- table fib_t/2.
fib_t(0,0).
fib_t(1,1).
fib_t(N,F) :- N>1, N1 is N-1, N2 is N-2,
              fib_t(N1,F1), fib_t(N2,F2), F is F1+F2.

fib_n(0,0).
fib_n(1,1).
fib_n(N,F) :- N>1, N1 is N-1, N2 is N-2,
              fib_n(N1,F1), fib_n(N2,F2), F is F1+F2.

Run the plain version and time it:

swipl -q -f fib.pl -g "time((fib_n(30,X), writeln(X)), halt)."

Run the tabled version:

swipl -q -f fib.pl -g "time((fib_t(30,X), writeln(X)), halt)."

You should see the tabled call finish in a few milliseconds while the plain call takes seconds or more. After the tabled run you can inspect memoization statistics:

swipl -q -f fib.pl -g "fib_t(30,_), statistics(table,Stats), writeln(Stats), halt."

The output shows roughly 31 tabled entries (fib/2 for N = 0..30).

Trade‑offs and Limitations

• Memory consumption grows with the number of distinct subgoal instances. For programs with little recursion the table overhead can outweigh speed gains.
• Tabling assumes a stratified program. Using cut (!) or negation as failure (\+) inside a tabled predicate can produce incorrect results or cause non‑termination.
• Some Prolog systems require explicit activation (e.g., SWI‑Prolog 8+ or XSB). Older versions ignore the :- table/1. directive.

Actionable Checklist

1. Confirm your Prolog supports tabling (SWI‑Prolog ≥ 8, XSB, or YAP with tabling).
2. Add :- table Pred/Arity. for each recursive predicate you want to memoize.
3. Re‑compile or reload the source.
4. Run a representative query and compare timing with statistics/2 or time/1.
5. If memory becomes a concern, abolish tables when they are no longer needed with :- abolish_table(Pred/Arity). or at runtime with abolish_table/1.

With these steps you can turn many exponential‑time recursive definitions into practical, linear‑time solutions while keeping the declarative style of Prolog.