Recursively-memoized implementation of the Ackermann formula as discussed on ComputerPhile (https://www.youtube.com/watch?v=i7sm9dzFtEI).

AckermannMemoized

public class AckermannFormulaMemoized
{
    public static long AckermannMemoized(long m, long n)
    {
        long ans = 0;
        string key = String.Format("{0},{1}", m, n);
        
        if (memory.ContainsKey(key)) {
            return memory[key];
        } else {
            if (m == 0) ans = (n+1);
            else if (n == 0) ans = Ackermann(m-1, 1);
            else ans = Ackermann(m-1, Ackermann(m, n-1));
            
            memory.Add(key, ans);
            return ans;
        }
    }
    
    // MEMORY CACHE
    // Keys are indexed as "m,n"
    // https://en.wikipedia.org/wiki/Ackermann_function
    private static Dictionary<string, long> memory = new Dictionary<string, long>()
    {
        { "0,0", 1 }, { "0,1", 2 }, { "0,2", 3 }, { "0,3", 4 }, { "0,4", 5 },
        { "1,0", 2 }, { "1,1", 3 }, { "1,2", 4 }, { "1,3", 5 }, { "1,4", 6 },
        { "2,0", 3 }, { "2,1", 5 }, { "2,2", 7 }, { "2,3", 9 }, { "2,4", 11 },
        { "3,0", 5 }, { "3,1", 13 }, { "3,2", 29 }, { "3,3", 61 }, { "3,4", 125 }
    };
}