using System;

using System.Collections.Generic;           

using System.Diagnostics;

​

public class Program

{

    public static void Main()

    {

        Func<uint, uint> fib = null;

        fib = x => x > 1 ? fib(x - 1) + fib(x - 2) : x;

        Stopwatch s = new Stopwatch();

        s.Start();

        Console.WriteLine(fib(37));

        Console.WriteLine("Without optimization: {0}", s.Elapsed);

        fib = fib.Memoize();

        s.Restart();

        Console.WriteLine(fib(37));

        Console.WriteLine("Without optimization: {0}", s.Elapsed);

    }

}

​

public static class FuncExtensions

{

    public static Func<A, R> Memoize<A, R>(this Func<A, R> f)

    {

        var d = new Dictionary<A, R>();

        return a =>

        {

            R r;

            if (!d.TryGetValue(a, out r))

            {

              r = f(a);

              d.Add(a, r);

            }

            return r;

        };

    }

}