Ackermann函数在C中的替代实现

Question

我用C编写了一个程序，它为用户输入的2个非负整数计算Ackermann值。程序检查整数是否为非负数，如果是，则计算它们的Ackermann值，然后请求新的输入或退出。这个程序在C语言中运行得很好，我对它没有问题。这是我的代码：

int ackermann(int m, int n){
        if (m == 0) return n + 1;
        if (n == 0) return ackermann(m - 1, 1);
        return ackermann(m - 1, ackermann(m, n - 1));
}

但是，实际上，为了满足大学课程的需要，我们使用了一个修改的C版本(基本上相同，但语法规则不同)，它模拟了MIPS汇编语言的语法和规则。更具体地说，我们使用寄存器来操作除数组和结构之外的所有数据。另外，我们不能使用for、while或do-while循环，而是使用if和goto语句。因此，我用这种语言编写了以下程序(正如我说的，它不过是具有不同语法的C)。我的问题是，它只适用于(x,0)和(0，y)用户输入(x和y是非负数)。它不适用于(4,1)，(3,2)以及所有没有零的输入。我知道，由于这些计算的大量叠加，它不能有效地工作在(10,10)这样的非常大的数字上。但是我希望它能适用于一些简单的输入，比如Ackermann(3,1) == 13。

//Registers --- The basic difference from C is that we use registers to manipulate data
int R0=0,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11,R12,R13,R14,R15,R16,R17,R18,R19,R20,R21,
R22,R23,R24,R25,R26,R27,R28,R29,R30,R31;

int ackermann(int m, int n){

    R4 = m;
    R5 = n;

    if(R4 != 0)
        goto outer_else;
    R6 = R5 + 1;
    return R6;

    outer_else:
        if(R5 != 0)
            goto inner_else;
        R7 = R4 - 1;
        R6 = ackermann(R7, 1);
        return R6;

        inner_else:
            R8 = R5 - 1;
            R9 = ackermann(R4, R8);
            R10 = R4 - 1;
            R6 = ackermann(R10, R9);
            return R6;
}

Answer 1

我认为您的问题是，这些寄存器值被定义为全局变量，它们是通过对ackermann()的内部调用来更新的，而外部调用依赖于这些值不改变。例如，查看注册版本的inner_else子句:它调用ackermann(R4, R8)，下一个语句依赖于R4的当前值，但递归调用在到达赋值语句之前更改了R4的设置。

有两个共同的解决办法：

1. 将寄存器定义为局部变量，并让编译器跟踪每个函数的调用状态。
2. 在输入到您的ackermann()函数时，手动保存所有寄存器的状态，然后在退出时恢复状态。

虽然解决方案1比较容易，但我想您的老师可能更喜欢解决方案2，因为它说明了编译器在生成的程序集代码中处理实际寄存器管理所使用的技术。