Ackermann Function quenstion.

[MasterHacker110]

I recently read about the Ackerman Function and thought I would do my own implementation of it:

#include <stdio.h>

long long int ackermann(long long int m, long long int n)
{
    if (m == 0) 
        return n + 1;
    if (n == 0) 
        return ackermann(m - 1, 1);

    return ackermann(m - 1, ackermann(m, n - 1));
}

int main()
{
    long long int m, n;
    for (m = 0; m <= 4; m++)
    {
        for (n = 0; n < 6 - m; n++)
        {
            printf("A(%d, %d) = %d\n", m, n, ackermann(m, n));
        }
    }

    getc(stdin);
    return 0;
}

I believe this code is correct. However, I have a problem. The program only generates the following:

A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(4, 0) = 13

After that it crashes. It cannot produce A(4, 1).
It seems that I am getting a stackoverflow. How do I fix this.

[Moschops]

Your ackermann function is recursive (I don't know if it's correct, just that it's recursive), and calls itself so many times that you run out of memory on the stack. The solution is to come up with a way to make it a lot less recursive, or increase the stack memory (which may not be something you can do on your operating system, and will only be holding the problem off a little longer anyway).

[MasterHacker110]

Thanks. It apears this problem only exists on Windows, not on Linux.

[Moschops]

Linux typically has a much larger stack. If you increase the values high enough, you'll hit the same problem. I seem to recall a default of 1MB on windows (using visual studio) and in Linux, it varies by system (command "ulimit -s" will show you the current setting). They can be changed, but generally if you're running out of stack, it's time to rethink the approach.