Memoised function

Rremember the answer that already been calculated so that no repeat calculation is ever made.

Example from fibonacci calculation

Normally we can calculate fibonacci of any integer > 0 by

fib(n)
if n < 2 then return 1
else return fib(n-1) + fib(n-2)

which is more or less followed from the definition of fibonacci.

The above method contains very large number of repeated calculation. Now let's try to memorise (or in computer science jargon, make a memoised function) answers that have already been calculated.

fibm(n)
if we already know the answer of fibm(n) return that value
else use fib(n) to calculate it and remember it.

To keep all known answers, we use an array indexed by n. To distinguish between "known" and "unknown" answers, -1 is used as marker because fib(n) is never a negative number.

f is an array of size n
f[i] = fib(n) if the answer is known
= -1 if unknown

initially f [.] must be filled with -1. This takes big-theta(n). Now we can write fibm()

fibm(n)
if f[n] != -1 then return f[n]
else a = fib(n); f[n] = a; return a

and fib(n) needs to be modified to memorise its answer by calling fibm(n) instead.

fib(n)
if n < 2 then return 1
else return fibm(n-1) + fibm(n-2)

such a beauty !
This two functions are used together and they are called co-recursive.

last update 22 July 2004