How to check Stack Usage when Calculating Ackermann

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();
}

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.

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.