How can I prevent my Ackerman function from overflowing the stack?

Question

Is there a way to keep my Ackerman function from creating a stack over flow is does it for relatively small numbers , i.e. (4,2). This is the error

{Cannot evaluate expression because the current thread is in a stack overflow state.}

private void  Button1Click(object sender, EventArgs e)
        {
            var t = Ackermann(4,2);
            label1.Text += string.Format(": {0}", t);
            label1.Visible = true;
        }

        int Ackermann(uint m, uint n)
        {
            if (m == 0)
                return  (int) (n+1);
            if (m > 0 && n == 0)
                return Ackermann(m - 1, 1);
            if (m > 0 && n > 0)
                return Ackermann(m - 1, (uint)Ackermann(m, n - 1));
            else
            {
                return -1;
            }
        }

Answer 1

The best way to avoid StackOverflowException is to not use the stack.

Let's get rid of the negative case, as it's meaningless when we call with uint. Alternatively, what follows here will also work if we make the negative test the very first thing in the method, before the other possibilities are considered:

First, we're going to need a bigger boat:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        if (m == 0)
            return  n+1;
        if (n == 0)
            return Ackermann(m - 1, 1);
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

Now success is at least mathematically possible. Now, the n == 0 case is a simple enough tail-call. Let's eliminate that by hand. We'll use goto because it's temporary so we don't have to worry about velociraptors or Dijkstra:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
    restart:
        if (m == 0)
            return  n+1;
        if (n == 0)
        {
            m--;
            n = 1;
            goto restart;
        }
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

This will already take a bit longer to blow the stack, but blow it, it will. Looking at this form though, note that m is never set by the return of a recursive call, while n sometimes is.

Extending this, we can turn this into an iterative form, while only having to deal with tracking previous values of m, and where we would return in the recursive form, we assign to n in our iterative form. Once we run out of ms waiting to be dealt with, we return the current value of n:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                stack.Push(m - 1);
                n = 1;
            }
            else
            {
                stack.Push(m - 1);
                stack.Push(m);
                --n;
            }
        }
        return n;
    }

At this point, we have answered the OP's question. This will take a long time to run, but it will return with the values tried (m = 4, n = 2). It will never throw a StackOverflowException, though it will end up running out of memory above certain values of m and n.

As a further optimisation, we can skip adding a value to the stack, only to pop it immediately after:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

This doesn't help us with stack nor meaningfully with heap, but given the number of loops this thing will do with large values, every bit we can shave off is worth it.

Eliminating goto while keeping that optimisation is left as an exercise for the reader :)

Incidentally, I got too impatient in testing this, so I did a cheating form that uses known properties of the Ackerman function when m is less than 3:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(m == 1)
                n = n + 2;
            else if(m == 2)
                n = n * 2 + 3;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

With this version, I can get a result of true for Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 after a little over a second (Mono, Release build, running on a Core i7). Given that the non-cheating version is consistent in returning the correct result for such values of m, I take this as reasonable evidence of the correctness of the previous version, but I'll leave it running and see.

Edit: Of course, I'm not really expecting the previous version to return in any sensible timeframe, but I thought I'd leave it running anyway and see how its memory use went. After 6 hours it's sitting nicely under 40MiB. I'm pretty happy that while clearly impractical, it would indeed return if given enough time on a real machine.

Edit: Apparently it's being argued that Stack<T> hitting its internal limit of 2³¹ items counts as a sort of "stack overflow", too. We can deal with that also if we must:

public class OverflowlessStack <T>
{
    internal sealed class SinglyLinkedNode
    {
        //Larger the better, but we want to be low enough
        //to demonstrate the case where we overflow a node
        //and hence create another.
        private const int ArraySize = 2048;
        T [] _array;
        int _size;
        public SinglyLinkedNode Next;
        public SinglyLinkedNode()
        {
            _array = new T[ArraySize];
        }
        public bool IsEmpty{ get{return _size == 0;} }
        public SinglyLinkedNode Push(T item)
        {
            if(_size == ArraySize - 1)
            {
                SinglyLinkedNode n = new SinglyLinkedNode();
                n.Next = this;
                n.Push(item);
                return n;
            }
            _array [_size++] = item;
            return this;
        }
        public T Pop()
        {
            return _array[--_size];
        }
    }
    private SinglyLinkedNode _head = new SinglyLinkedNode();

    public T Pop ()
    {
        T ret = _head.Pop();
        if(_head.IsEmpty && _head.Next != null)
            _head = _head.Next;
        return ret;
    }
    public void Push (T item)
    {
        _head = _head.Push(item);
    }
    public bool IsEmpty
    {
        get { return _head.Next == null && _head.IsEmpty; }
    }
}
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
    var stack = new OverflowlessStack<BigInteger>();
    stack.Push(m);
    while(!stack.IsEmpty)
    {
        m = stack.Pop();
    skipStack:
        if(m == 0)
            n = n + 1;
        else if(m == 1)
            n = n + 2;
        else if(m == 2)
            n = n * 2 + 3;
        else if(n == 0)
        {
            --m;
            n = 1;
            goto skipStack;
        }
        else
        {
            stack.Push(m - 1);
            --n;
            goto skipStack;
        }
    }
    return n;
}

Again, calling Ackermann(4, 2) returns:

Which is the correct result. The stack structure used will never throw, so the only limit remaining is the heap (and time of course, with large enough inputs you'll have to use "universe lifetime" as a unit of measurement...).

Since the way it's used is analogous to the tape of a Turing machine, we're reminded of the thesis that any calculable function can be calculated on a Turing machine of sufficient size.

Answer 2

Use memoization. Something like:

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

private static int Pack(int m, int n) {
 return m * 1000 + n;
}

private static int Ackermann(int m, int n) {
  int x;
  if (!a.TryGetValue(Pack(m, n), out x)) {
    if (m == 0) {
      x = n + 1;
    } else if (m > 0 && n == 0) {
      x = Ackermann(m - 1, 1);
    } else if (m > 0 && n > 0) {
      x = Ackermann(m - 1, Ackermann(m, n - 1));
    } else {
      x = -1;
    }
    a[Pack(m, n)] = x;
  }
  return x;
}

However, this example only shows the concept, it will still not give the correct result for Ackermann(4, 2), as an int is way too small to hold the result. You would need an integer with 65536 bits instead of 32 for that.