  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& lt; int,  int&
gt;  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 urlLink 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 urlLink Haskell ,  have something called monads (
or triples)  which come from urlLink 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.
