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 which stores all values that it finds.
In[1]:=
Click for copyable input
Here are the end conditions for the recursive function .
In[2]:=
Click for copyable input
Out[2]=
Here is the original definition of .
This computes . The computation involves finding the sequence of values , , .
In[4]:=
Click for copyable input
Out[4]=
All the values of found so far are explicitly stored.
If you ask for again, the Wolfram Language can just look up the value immediately; it does not have to recompute it.
In[6]:=
Click for copyable input
Out[6]=

You can see how a definition like works. The function is defined to be the "program" . When you ask for a value of the function , the "program" is executed. The program first calculates the value of , then saves the result as .

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.