`asserta`

), that has been inferred
during the execution of your program, in the Prolog database,
to avoid possibly having to infer the same fact again, later
in the execution of the program.
Whether this is worth doing depends on the nature of the problem.
If facts are regularly re-inferred (possibly as a consequence
of a recursive solution), then memoisation could be a very good
idea. Some algorithms perform double or multiple recursion (that
is, they "recurse" on more than one variable), and both recursive
branches can end up re-calculating the same thing, leading in
some cases to exponential growth in the number of sub-cases as
the size of the problem grows. The classic example is the
recursive computation of the *n*-th
Fibonacci number, which is (recursively) defined* by:

f_{0}=f_{1}= 1, and,

forn> 1,f=_{n}f_{n-2}+f_{n-1}.

* Note that a non-recursive expression for
*f _{n}* is also known - something we
ignore here since this example is about recursion.

As can be seen (or rather, extrapolated) from the diagram, the number of calls grows exponentially, and the Fibonacci numbers rapidly become infeasible to calculate by the naive recursive program:

fib_naive(N, Result) :- N > 1, Nminus2 is N - 2, Nminus1 is N - 1, fib_naive(Nminus1, FibNminus2), fib_naive(Nminus1, FibNminus1), Result is FibNminus1 + FibNminus2.However, by memoising, the computation becomes perfectly feasible for much larger values of

fib_memo(0, 1). fib_memo(1, 1). fib_memo(N, Result) :- N > 1, Nminus2 is N - 2, Nminus1 is N - 1, fib_memo(Nminus2, Fib2Nminus2), fib_memo(Nminus1, Fib2Nminus1), Result is Fib2Nminus1 + Fib2Nminus2, asserta((fib_memo(N, Result) :- !)).

Note the use of `asserta`

to
store the memoised value at the *start* of the collection of
facts for `fib_memo`

, so that it will be checked
*before* trying the rule. Note also the cut
(`!`

) at the end of the `assserta`

-ed rule,
which stops the algorithm from backtracking and trying the rule
after it has found a solution using the memoised value(s).
This cut is *necessary*, as otherwise, while the first solution
would be found fast, the code would repeatedly find the same solution
a huge number of times, taking a huge amount of computing time.