c - 计算阿克曼时如何检查堆栈使用情况

Question

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

我已经尝试了一些方法来捕获堆栈溢出，据我所知，c++ 没有我可以捕获的 stackoverflowexception。 try-catch block 不起作用。在下面的代码中，我使用 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();
}

Answer 1

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

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

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

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

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

如果您必须使用递归，请通过创建您自己的堆栈数据结构来手动执行此操作，该结构分配在堆上而不是堆栈空间中。用它来跟踪你在递归中的位置。推送和弹出以及递归，而不是通过嵌套方法调用递归。

但最后，您无论如何都不应该使用递归来计算阿克曼。