How to check Stack Usage when Calculating Ackermann

Question

I'm learning about my system's ability to calculate Ackermann's algorithm both the two and three parameter version. For very small values of m and n, my system will calculate and print results returning from A0 and A1 method calls. However anything higher than 3 or 4 does not return and freezes the terminal I'm using atm. My problem is that I do determine for what values of m and n my machine can compute.

I have tried a few things to catch a stack overflow, for all i know c++ doesn't have a stackoverflowexception I can catch. try-catch blocks don't work. In the below code, I use getrlimit() to find the stack limit, create a address location in main gStackRef. I call checkStack recursively checking the local variable pointer to gStackLimit.

Is there a better way of checking my stack usage in relation to recursive methods? Also I do i check for segment faults? I'll let you know I'm running on a unix terminal.

#include <cstdlib>
#include <iostream>


#define _XOPEN_SOURCE_EXTENDED 1
#include <sys/resource.h>

int getrlimit(int resource, struct rlimit *rlp);

using namespace std;

int * gStackRef;
int gStackLimit;

void checkStack(void);

int main(int argc, char *argv[])
{
        int temp = 0;
        gStackRef = &temp;
        rlimit myl;
        getrlimit(RLIMIT_STACK, &myl);
        gStackLimit = (myl.rlim_cur / 3 * 8 / 10) ;/* modified for segment fault */
        cout << gStackLimit << "\n";
        checkStack();
}

void checkStack()
{
        int temp = 0;
        int* pVariableHere = &temp;
        size_t stackUsage = gStackRef - pVariableHere;
        printf("Stack usage: %d / %d \n", stackUsage, gStackLimit);
        if(stackUsage > gStackLimit) return;
        else checkStack();
}

1. Fixed title spelling error. 2. Retagged C++ -> C; there's no C++ going on here. 3. Tagged with POSIX, because that's the API you're obviously building on top of. (For what it's worth, Ackermann is probably best calculated using some form of dynamic programming rather than recursion) — Billy ONeal, Sep 27 '11 at 18:32
By dynamic programming, are you suggesting that I try saving returned values of A0 and A1 to a table? That way I can check the table before doing another recursive call and save myself some space. — ASLilly, Sep 27 '11 at 18:39
Yes, dynamic programming is a table driven algorithm solving method. See the wikipedia article linked in my answer for more details. AFAIK you shouldn't need more than `m*n` space and time to calculate this using a table. (I could be wrong though; I've not implemented it myself) Consider a similar case, the Fibonacci Sequence, which takes exponential time calculated recursively but only linear time calculated using dynamic programming. — Billy ONeal, Sep 27 '11 at 18:41

score 2 · Answer 1 · answered Sep 27 '11 at 18:36

However anything higher than 3 or 4 does not return and freezes the terminal I'm using atm.

That's kind of the point of the Ackermann function. It grows extremely rapidly. For m >= 4 and n >= 3, if you're calculating A(m, n) recursively, I doubt your function will return before you're dead.

I have tried a few things to catch a stack overflow, for all i know c++ doesn't have a stackoverflowexception I can catch.

Of course not. The process is out of stack space. It should be torn down immediately.

Is there a better way of checking my stack usage in relation to recursive methods?

If you have to use recursion, do it manually by creating your own stack data structure that is allocated on the heap instead of in the stack space. Use that to keep track of where you are in the recursion. Push and pop and as you recurse, instead of recursing by nested method calls.

But at the end, you shouldn't be using recursion to calculate Ackermann anyway.

can you elaborate on why you shouldn't be using recursion to calculate Ackermann? I thought it couldn't be done using iterative loops. — Kelly S. French, Dec 07 '17 at 02:13

score 0 · Answer 2 · edited May 23 '17 at 12:06

I have tried a few things to catch a stack overflow, for all i know c++ doesn't have a stackoverflowexception I can catch. try-catch blocks don't work. In the below code, I use getrlimit() to find the stack limit, create a address location in main gStackRef. I call checkStack recursively checking the local variable pointer to gStackLimit.

POSIX does not have a "safe" way of detecting a stack overflow. Stack Overflows result in SIGSEGV signals, which you (generally) should not catch because they also are indicative of general segmentation faults, which should crash your program. Windows environments can deal with stack overflows safely, using EXCEPTION_STACK_OVERFLOW -- but in such cases what Windows is doing is merely putting a guard page at the end of the stack and notifying with SEH. If you use up the guard page (after ignoring the SEH exception), then your program gets terminated (just as it would in POSIX-land).

Is there a better way of checking my stack usage in relation to recursive methods? Also I do i check for segment faults? I'll let you know I'm running on a unix terminal.

No. Even what you're doing has undefined behavior. On some machines the stack grows up. On some machines the stack grows down. The compiler may insert any amount of slop space in between two methods. Technically, the compiler could implement things such that there were two separate stacks, located in two completely different memory segments, and still be conformant.

If you want to calculate Ackermann in a stack safe manner, either use an explicit stack structure allocated from the heap, or use dynamic programming.

How to check Stack Usage when Calculating Ackermann

2 Answers2