2

我正在了解我的系统计算阿克曼算法的两个和三个参数版本的能力。对于非常小的 m 和 n 值，我的系统将计算并打印从 A0 和 A1 方法调用返回的结果。但是任何高于 3 或 4 的东西都不会返回并冻结我正在使用 atm 的终端。我的问题是我确实确定了我的机器可以计算的 m 和 n 的值。

我已经尝试了一些方法来捕获堆栈溢出，因为我所知道的 C++ 没有我可以捕获的 stackoverflowexception。try-catch 块不起作用。在下面的代码中，我使用 getrlimit() 来查找堆栈限制，在主 gStackRef 中创建一个地址位置。我调用 checkStack 递归地检查指向 gStackLimit 的局部变量指针。

有没有更好的方法来检查与递归方法相关的堆栈使用情况？我还要检查段故障吗？我会让你知道我在一个 unix 终端上运行。 

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

2 回答 2

2

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.

于 2011-09-27T18:36:29.617 回答
0

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.

于 2011-09-27T18:37:09.463 回答