Functions That Remember Values They Have Found

When you make a function definition using :=, the value of the function is recomputed every time you ask for it. In some kinds of calculations, you may end up asking for the same function value many times. You can save time in these cases by having the Wolfram Language remember all the function values it finds. Here is an "idiom" for defining a function that does this.

f[x_]:=f[x]=rhsdefine a function which remembers values that it finds

Defining a function that remembers values it finds.

This defines a function f which stores all values that it finds:
Click for copyable input
Here are the end conditions for the recursive function f:
Click for copyable input
Here is the original definition of f:
Click for copyable input
This computes f[5]. The computation involves finding the sequence of values f[5], f[4], f[2]:
Click for copyable input
All the values of f found so far are explicitly stored:
Click for copyable input
If you ask for f[5] again, the Wolfram Language can just look up the value immediately; it does not have to recompute it:
Click for copyable input

You can see how a definition like f[x_]:=f[x]=f[x-1]+f[x-2] works. The function f[x_] is defined to be the "program" f[x]=f[x-1]+f[x-2]. When you ask for a value of the function f, the "program" is executed. The program first calculates the value of f[x-1]+f[x-2], then saves the result as f[x].

It is often a good idea to use functions that remember values when you implement mathematical recursion relations in the Wolfram Language. In a typical case, a recursion relation gives the value of a function with an integer argument in terms of values of the same function with arguments , , etc. The Fibonacci function definition used above is an example of this kind of recursion relation. The point is that if you calculate say by just applying the recursion relation over and over again, you end up having to recalculate quantities like many times. In a case like this, it is therefore better just to remember the value of , and look it up when you need it, rather than having to recalculate it.

There is of course a tradeoff involved in remembering values. It is faster to find a particular value, but it takes more memory space to store all of them. You should usually define functions to remember values only if the total number of different values that will be produced is comparatively small, or the expense of recomputing them is very great.