0

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.

2
Contributors
3
Replies
19
Views
2 Years
Discussion Span
Last Post by Moschops
0

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).

Edited by Moschops

0

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.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.