Demo implementation of the Ackermann Function in C# using dynamic programming.

DynamicAckermannFunction.cs

using System;
using System.Threading;
using System.Collections.Generic;

namespace ConsoleApplication1
{
	class Program
	{
		private static int answer;
		private static int iterations = 0;
		private static int maxdepth = 0;

		private struct Key
		{
			public int m;
			public int n;

			public Key(int m, int n)
			{
				this.m = m;
				this.n = n;
			}

			public override bool Equals(object obj)
			{
				if (obj is Key)
					return m == ((Key)obj).m && n == ((Key)obj).n;
				else
					return false;
			}
		}

		private static Dictionary<Key, int> dynamiclist = new Dictionary<Key, int>();

		static void Main(string[] args)
		{
			Thread t = new Thread(AckermannMain, 512 * 1024 * 1024);
			t.Start();
			t.Join();

			Console.Out.WriteLine("Answer: " + answer);
			Console.Out.WriteLine("Iterations: " + iterations);
			Console.Out.WriteLine("Max Depth: " + maxdepth);
			Console.In.ReadLine();
		}

		static void AckermannMain()
		{
			answer = Ackermann(4, 2, 0);
		}

		static int Ackermann(int m, int n, int depth)
		{
			Console.Out.WriteLine(depth + "," + m + "," + n);

			var key = new Key(m, n);
			if (dynamiclist.ContainsKey(key))
				return dynamiclist[key];

			depth++;
			maxdepth = Math.Max(depth, maxdepth);
			iterations++;

			int retval;

			if (m == 0)
				retval = n + 1;
			else if (m > 0 && n == 0)
				retval = Ackermann(m - 1, 1, depth);
			else
			{
				int rec = Ackermann(m, n - 1, depth);
				dynamiclist[new Key(m, n - 1)] = rec;
				retval = Ackermann(m - 1, rec, depth);
			}

			dynamiclist[key] = retval;
			return retval;
		}
	}
}

cool