Ackerman without stack overflow

ackermann.cs

using System;
using System.Collections.Generic;

namespace Trampoline
{
    class Program
    {
        static void Main()
        {
            for (long m = 0; m <= 3; ++m)
            {
                for (long n = 0; n <= 7; ++n)
                {
                    Console.WriteLine("Ackermann({0}, {1}) = {2}, {3}", m, n, AckermannRecurs(m, n), Trampoline(Ackermann(m, n)));
                }
            }
            Console.WriteLine("Ackermann({0}, {1}) = {2}", 4, 2, Trampoline(Ackermann(4, 2)));
            Console.ReadLine();
        }

        public static long AckermannRecurs(long m, long n)
        {
            if (m > 0)
            {
                if (n > 0)
                    return AckermannRecurs(m - 1, AckermannRecurs(m, n - 1));
                else if (n == 0)
                    return AckermannRecurs(m - 1, 1);
            }
            else if (m == 0)
            {
                if (n >= 0)
                    return n + 1;
            }
            throw new ArgumentOutOfRangeException();
        }

        public static object Ackermann(dynamic m, dynamic n)
        {
            if (m > 0)
            {
                if (n > 0)
                    return Tuple.Create(new Func<object>(()=>Ackermann(m, n - 1)), new Func<object,object>((x) => Ackermann(m - 1, x)));
                if (n == 0)
                    return new Func<object>(() => Ackermann(m - 1, 1));
            }
            else if (m == 0)
            {
                if (n >= 0)
                    return n + 1;
            }
            throw new ArgumentOutOfRangeException();
        }

        static Stack<Func<object, object>> waiters = new Stack<Func<object, object>>();
        private static long Trampoline(dynamic result)
        {
            while (true)
            {
                if (result is Func<object>)
                {
                    result = result.Invoke();
                }
                else if (result is Tuple<Func<object>, Func<object, object>>)
                {
                    var arg = result.Item1.Invoke();
                    if (!(arg is Func<object>) && !(arg is Tuple<Func<object>, Func<object, object>>)) result = result.Item2.Invoke(arg);
                    else
                    {
                        waiters.Push(result.Item2);
                        result = arg;
                    }
                }
                else
                {
                    if (waiters.Count == 0) return result;
                    result = waiters.Pop().Invoke(result);
                }
            }
        }

    }
}

old.cs

using System;

namespace Ack
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			for (long m = 0; m <= 3; ++m)
	        {
	            for (long n = 0; n <= 4; ++n)
	            {
	                Console.WriteLine("Ackermann({0}, {1}) = {2}, {3}", m, n, AckermannRecurs(m, n), Ackermann.Solve(m,n));
	            }
	        }
			Console.WriteLine("Ackermann({0}, {1}) = {2}", 4, 2, AckermannRecurs(4,3));
		}
		
	    public static long AckermannRecurs(long m, long n)
	    {
	        if(m > 0)
	        {
	            if (n > 0)
	                return AckermannRecurs(m - 1, AckermannRecurs(m, n - 1));
	            else if (n == 0)
	                return AckermannRecurs(m - 1, 1);
	        }
	        else if(m == 0)
	        {
	            if(n >= 0) 
	                return n + 1;
	        }
	 	        throw new System.ArgumentOutOfRangeException();
	    }
	}
	
	public enum State
	{
		Created, Args, Recursion, Done
	}
	
	public class Ackermann{
		public long m;
		public long n;
		public Ackermann Recursion;
		public Ackermann RecursionArg;
		public Ackermann Parent;
		public long Result;
		public State CurrentState = State.Created;
		
		public Ackermann (long m, long n)
		{
			this.m = m;
			this.n = n;
		}
		
		public static long Solve(long x, long y)
		{
			var current = new Ackermann(x,y);	
			while (true) {
				if (current.CurrentState == State.Done) 
				{
					if (current.Parent == null) return current.Result;
					if (current.Parent.CurrentState == State.Args)
					{
						current.Parent.CurrentState = State.Recursion;
						current.Parent.Recursion = new Ackermann(current.Parent.m-1, current.Result);
						current.Parent.Recursion.Parent = current.Parent;
						current.Parent.RecursionArg = null;
					}
					else if (current.Parent.CurrentState == State.Recursion)
					{
						current.Parent.CurrentState = State.Done;
						current.Parent.Result = current.Result;
						current.Parent.Recursion = null;
					}
					current = current.Parent;
					
					continue;
				}
				if (current.CurrentState == State.Created) 
				{
					current.CurrentState = State.Done;					
					if(current.m > 0)
			        {
			            if (current.n > 0)
						{
							current.CurrentState = State.Args;
							current.RecursionArg = new Ackermann(current.m,current.n-1);
							current.RecursionArg.Parent = current;
			                
						}
			            else if (current.n == 0)
						{
							current.CurrentState = State.Args;
							current.RecursionArg = new Ackermann(0,0);
							current.RecursionArg.Parent = current;
						}
			        }
			        else if(current.m == 0)
			        {
			            if(current.n >= 0) 
			                current.Result =  current.n + 1;
			        }
					
					
					
					continue;
				}
				if (current.CurrentState == State.Args) 
				{
					current = current.RecursionArg;
					continue;
				}
				if (current.CurrentState == State.Recursion) 
				{
					current = current.Recursion;
					continue;
				}
			}
		}
	}
	
}