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:
f0 = f1 = 1, and,
for n > 1, fn = fn-2 + fn-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 n:
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
store the memoised value at the start of the collection of
fib_memo, so that it will be checked
before trying the rule. Note also the cut
!) at the end of the
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.
See also assert, dynamic.