C语言 计算Ackermann时如何检查Stack Usage

Question

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

我已经尝试了一些事情来捕获堆栈溢出，因为我知道c++没有我可以捕获的stackoverflowexception。Try-catch块不起作用。在下面的代码中，我使用getrlimit()来查找堆栈限制，在main 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();
}

Answer 1

然而，任何高于3或4的东西都不会返回并冻结我正在使用atm的终端。

这就是Ackermann函数的意义所在。它生长得非常快。对于m >= 4和n >= 3，如果你递归地计算A(m, n)，我怀疑你的函数会在你死之前返回。

我已经尝试了一些方法来捕获堆栈溢出，因为我知道c++没有我可以捕获的stackoverflowexception。

当然不是。进程的堆栈空间不足。应该立即拆除。

是否有更好的方法来检查与递归方法相关的堆栈使用情况?

如果必须使用递归，可以手动创建自己的堆栈数据结构，该结构是在堆上而不是在堆栈空间中分配的。用它来跟踪你在递归中的位置。Push和pop和递归，而不是通过嵌套方法调用递归。

但是最后，你不应该用递归来计算Ackermann

Answer 2

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

POSIX没有一种"安全"的方法来检测堆栈溢出。堆栈溢出导致SIGSEGV信号，您(通常)不应该捕获这些信号，因为它们也指示了一般的分段错误，这些错误应该使程序崩溃。Windows环境可以安全地处理堆栈溢出，使用EXCEPTION_STACK_OVERFLOW——但是在这种情况下，Windows所做的只是在堆栈的末尾放置一个保护页并使用SEH通知。如果您用光了保护页(在忽略SEH异常之后)，那么您的程序将被终止(就像在posix环境中一样)。

是否有更好的方法来检查与递归方法相关的堆栈使用情况?我也检查段故障吗?我会让你知道我在unix终端上运行。

。甚至你正在做的事情也有未定义的行为。在某些机器上，堆栈会增长。在一些机器上，堆栈变小了。编译器可以在两个方法之间插入任意数量的倾斜空间。从技术上讲，编译器可以实现这样的事情:有两个独立的堆栈，位于两个完全不同的内存段，并且仍然是一致的。

如果你想以堆栈安全的方式计算Ackermann，要么使用从堆中分配的显式堆栈结构，要么使用动态规划。