CODEWITHSUNDEEP
c++recursion
User_67128
User_67128

Reputation: 1250

Finding the value of Recursive Ackermann Function

What is wrong in my code? It doesn't return the correct answer,

#include <iostream>
using namespace std;

int ack(int m, int n)
{
    if (m == 0) return n + 1;

    if(n == 0) return ack(m - 1, 1);

    return ack(m - 1, ack(m, n - 1));

}

int main()
{
    cout << ack(4, 1) << endl;
    return 0;
}

Here is the output:

enter image description here

Thanks.

Upvotes: 0

Views: 321

Answers (1)

cdlane
cdlane

Reputation: 41872

Compiling it with a C compiler, instead of C++, your ack() function returned correctly, 65533, for me in about 20 seconds.

Using a recursive algorithm from RosettaCode that isn't doubly recursive like yours, returns the correct value in about 10 seconds:

int ack(int m, int n)
{
    for (; m > 0; m--) {
        n = (n == 0) ? 1 : ack(m, n - 1);
    }

    return n + 1;
}

Since you're not going to reach higher Ackermann values with this code, I don't see the point in going much faster.

Upvotes: 1

Related Questions