It's ... oh, why not let the docs speak:
tutorial/FunctionsThatRememberValuesTheyHaveFound
(in Doc center)
Edit
You may also find additional information by searching for "memoization" on this site. This has always been a great trick to avoid having to re-evaluate the result of a computationally intensive function call. In the above link, it is also used to do recursion.
I'll try to explain things without the added complication of recursion: The basic idea is that when you define a function using
f[x_]:= x^2
you are using x as the name of a pattern playing the role of a dummy variable. The := (meaning SetDelayed) has the property of leaving whatever is on the right-hand side unevaluated until it's needed, and this happens when a pattern matching the left side is encountered, say, f[4].
To make Mathematica remember things, you can't assign a value to a pattern, so you would normally say
f[4]=16
Now such definitions are found by Mathematica before it looks for matching pattern definitions such as f[x_]:=x^2 above. So in other words, if I type f[4] after having executed the above two lines, my "function definition" doesn't actually have to be used at all because the system already knows the result for the specific value 4.
The memoization trick now combines the above lines, which would lead to
f[x_]:=f[x]=x^2
The right-hand side of SetDelayed is now telling us to take whatever was passed in through the dummy variable x and assign this to f[x] using Set (the = sign). The result of that last operation is that a "non-pattern" f[x] with a specific new value of x has been defined for later use, and the value that got assigned to that is also returned as the replacement for the pattern f[x_] (i.e., the function value in the initial function call).
Whenever a new x is passed to f[x], we now get a new "permanent" definition added to the memory so that the function (the pattern) doesn't need to be evaluated again for that x.
It's best to play around with this yourself by defining a function along the lines above, and then periodically checking what Mathematica knows about your function by typing ?f.