Memoization is a name for caching the results of a function. If the result of a function depends only on its arguments (it does not look to other external variables, does not use static local variables etc.) then you can attach a cache that maps function parameter values to the results. Doing so can dramatically improve the computing time for some recursive functions because complexity changes - usualy from exponential to polinomial. In an imperative language you would do something like:

map<int, int> fibonacci_cache;
int fibonacci(int n)
{
   if (fibonacci_cache[n] != 0) return fibonacci_cache[n];
   if (n == 0) return 0;
   if (n == 1) return 1;
   return (fibonacci_cache[n] = fibonacci(n-1) + fibonacci(n-2));
}

This solution has complexity O(n log n), much better than O(2^n) without memoization. If you use a regular array instead of a map (balanced binary tree) as the cache you can even go to O(n). Of course, there are more efficient ways of computing fibonacci numbers, but here I discuss only memoization. An interesting problem is how to do memoization in a pure functional language (that is, without side-effects). A solution is to pass the cache as a parameter and also return it. This solution was suggested by (L.x.xx)(L.x.xx) at TopCoder RoundTables forums; he said the idea came from how side-effects are represented in denotational semantics. Here is an example implementation in OCaml (thanks to bogklug for some improvements of the code):

module OrderedInt =
struct
  type t = int
  let compare x y = compare
end;;

module AssocInt = Map.Make (OrderedInt);;

let rec fibr = function
  | 0, mem -> 0, mem
  | 1, mem -> 1, mem
  | n, mem ->
      try AssocInt.find n mem, mem with
      | Not_found ->
	  let res1, mem1 = fibr ((n - 1), mem) in
	  let res2, mem2 = fibr ((n - 2), mem1) in
	  res1 + res2, AssocInt.add n (res1 + res2) mem2
;;
let fib n = fst fibr (n, AssocInt.empty);;

Something similar can be done in any pure functional language. Some of them, like Haskell, have something called monads (or triples) which come from category theory. Monads provide an alternative way of doing memoization. Unfortunatelly I don't understand this yet. But I'll come back when I will.