C++ Implementation of Ackermann Function

Today we will learn about the famous Ackermann recursion function using C++ program.

The Ackermann function is named after Wilhelm Ackermann, this function defines exactly how there can exist a function that can only be executed recursively and provided a counterexample to the belief that every function that is computed can be computed primitive recursively.

It is an exponential function and hence with every step, its complexity increases many fold.

The function is in fact so complex that depending on the input value it is only possible to compute up to certain steps within an even an extended time period.

The following can be understood through the code –

Ackermann Function in C++

#include <iostream> 
using namespace std; 
  
int ack(int m, int n) 
{ 
    if (m == 0){ 
        return n + 1; 
    } 
    else if((m > 0) && (n == 0)){ 
        return ack(m - 1, 1); 
    } 
    else if((m > 0) && (n > 0)){ 
        return ack(m - 1, ack(m, n - 1)); 
    } 
} 
  
int main() 
{ 
    int A; 
    A = ack(1, 2); 
    cout << A << endl; 
    return 0; 
}

Below is the output of the above program after we run the program:

4

In this case, to solve the query of ack(1,2) it takes a high number of recursive steps and where the time complexity is actually O(mack(m, n)) to compute ack(m, n).

The space complexity is O(m) to compute ack(m, n)

So you can well imagine if the number is increased say if we have to compute a number like (4,1) takes approximately 3 minutes to compute the value of ack(4,1) which comes out to be 65533.

The next number which is (4,2) will actually take hours and hours to compute because of its exponentially increasing complexity.

Leave a Reply