Function Memoization

Recursion is a great, but some times unnecessarily expensive. Take the case of Fibonacci: we've just computed the previous results for the series, why compute them again?

Here's a nice sample:

...we can Memoize fib so that if it calls fib again with the same argument then it will not recalculate but instead use the previous result. This will move our exponential function to a linear one at the cost of linear space to store the previous results (we could possibly use a weak reference hash map instead to solve problems with space if they existed). In fact, subsequent calls to fib with previously computed values will be evaluated in constant time.

 
Func fib = null;
fib = n => n  > 1 ? fib(n - 1) + fib(n - 2) : n;
fib =  fib.Memoize();

and here is the magic:

public static Func Memoize(this Func f)
{
 var map = new Dictionary();
 return a =>
   {
     R value;
     if (map.TryGetValue(a, out value))
       return value;
     value = f(a);
     map.Add(a, value);
     return value;
   };
}