双重递归函数

Question

我想编写 S. Wolf 在 A Tour Through Mathematical Logic 中定义的函数（阿克曼函数的修改版本），如下所示：

A(0,n)=n+1 for every n

A(1,0)=2

A(2,0)=0

A(m+3,0)=1 for every m

A(m+1,n+1)=A(m,A(m+1,n)) for every m and n

为了使程序更快，我使用了

A(1,n)=n+2
A(2,n)=2n
A(3,n)=2^n

代码如下：

#include <iostream>
#include <cmath>

using namespace std;

long long A(long long m, long long n)
{
    if(m==0)
        return n+1;
    else if(m==1)
        return n+2;
    else if(m==2)
        return 2*n;
    else if(m==3)
        return pow(2,n);
    else if(m>=4 && n==0)
        return 1;
    else
        return A(m-1,A(m,n-1));
}

int main(void)
{
    long long m,n;
    cout << "m=";
    cin >> m;
    cout << "n=";
    cin >> n;
    cout << "A(m,n)=" << A(m,n) << endl;
    return 0;
}

它似乎工作正常：手动 A(5,3)=2^16 这就是我得到的结果。然而，程序输出 A(5,4)=4 和 A(5,5)=2^16，而正确的结果非常大。我无法在我的代码中发现错误。你能告诉我有什么问题吗？提前谢谢你。

Answer 1

正如 NeilButterworth 在评论中所说，错误结果背后的原因是溢出。

正如 RobertAndrzejuk 在评论中所建议的那样，我使用了另一个库 (GMP) 来处理大量数据。这是新代码：

#include <iostream>
#include <cmath>
#include <gmpxx.h>

using namespace std;

mpz_class pow(int a,mpz_class b)
{
    mpz_class res=1;
    for(int i=1;i<=b;++i)
        res*=a;
    return res;
}

mpz_class A(mpz_class m, mpz_class n)
{
    if(m==0)
        return n+1;
    else if(m==1)
        return n+2;
    else if(m==2)
        return 2*n;
    else if(m==3)
        return pow(2,n);
    else if(m>=4 && n==0)
        return 1;
    else
        return A(m-1,A(m,n-1));
}

int main(void)
{
    mpz_class m,n;
    cout << "m=";
    cin >> m;
    cout << "n=";
    cin >> n;
    cout << "A(m,n)=" << A(m,n) << endl;
    return 0;
}

该程序能够计算出 A(4,5)，它有 19729 个数字（我无法验证结果是否正确，但 A(4,5) 的确切数字确实是 19729所以我相信结果是正确的）。然后程序在我要求它计算 A(5,4) 时指示分段错误，这真的很大。

双重递归函数

A double recursive function

c++

recursion

ackermann