Implementation of Ackermann Function in Python

In this tutorial, we will find out what Ackermann Function is and how to implement it in Python. This function is developed to show that there is the possibility of recursive function to be not primitive recursive.

There could be a function that could demand implementation without for loop, there could be a function where the upper limit may not be known at the time of implementation. So, what is an Ackermann function, and how to implement it?  Let’s Find out.

What is an Ackermann function?

It is a function that works on recursivity and takes two numbers as input. Its implementation has the following conditions:
Let Ackermann(m,n) be the required function,
So, it can be calculated as :
if m=0 then Ackermann(m,n)= n+1,
if m>0, n=0 then Ackermann(m,n)= Ackermann(m-1,n) and
if m>0, n>0 then Ackermann(m,n)= Ackermann(m-1,Ackermann(m,n-1))

Implementation:

Using the conditions given above the code for the Ackermann function can be easily written in Python as follows:
def A(m, n, s ="% s"): 
    print(s % ("A(% d, % d)" % (m, n))) 
    if m == 0: 
        return n + 1
    if n == 0: 
        return A(m - 1, 1, s) 
    n2 = A(m, n - 1, s % ("A(% d, %% s)" % (m - 1))) 
    return A(m - 1, n2, s) 
  
print("\nResult = {}".format( A(2, 3)))

 

Output:

The given output is for values of m and n to be 2 and 3 respectively. The result is 9.
A( 2, 3) 
A( 1, A( 2, 2)) 
A( 1, A( 1, A( 2, 1))) 
A( 1, A( 1, A( 1, A( 2, 0)))) 
A( 1, A( 1, A( 1, A( 1, 1)))) 
A( 1, A( 1, A( 1, A( 0, A( 1, 0))))) 
A( 1, A( 1, A( 1, A( 0, A( 0, 1))))) 
A( 1, A( 1, A( 1, A( 0, 2)))) 
A( 1, A( 1, A( 1, 3))) 
A( 1, A( 1, A( 0, A( 1, 2)))) 
A( 1, A( 1, A( 0, A( 0, A( 1, 1))))) 
A( 1, A( 1, A( 0, A( 0, A( 0, A( 1, 0)))))) 
A( 1, A( 1, A( 0, A( 0, A( 0, A( 0, 1)))))) 
A( 1, A( 1, A( 0, A( 0, A( 0, 2))))) 
A( 1, A( 1, A( 0, A( 0, 3)))) 
A( 1, A( 1, A( 0, 4))) 
A( 1, A( 1, 5)) 
A( 1, A( 0, A( 1, 4))) 
A( 1, A( 0, A( 0, A( 1, 3)))) 
A( 1, A( 0, A( 0, A( 0, A( 1, 2))))) 
A( 1, A( 0, A( 0, A( 0, A( 0, A( 1, 1)))))) 
A( 1, A( 0, A( 0, A( 0, A( 0, A( 0, A( 1, 0))))))) 
A( 1, A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, 1))))))) 
A( 1, A( 0, A( 0, A( 0, A( 0, A( 0, 2)))))) 
A( 1, A( 0, A( 0, A( 0, A( 0, 3))))) 
A( 1, A( 0, A( 0, A( 0, 4)))) 
A( 1, A( 0, A( 0, 5))) 
A( 1, A( 0, 6)) 
A( 1, 7) 
A( 0, A( 1, 6)) 
A( 0, A( 0, A( 1, 5))) 
A( 0, A( 0, A( 0, A( 1, 4)))) 
A( 0, A( 0, A( 0, A( 0, A( 1, 3))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, A( 1, 2)))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, A( 1, 1))))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, A( 1, 0)))))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, 1)))))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, 2))))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, A( 0, 3)))))) 
A( 0, A( 0, A( 0, A( 0, A( 0, 4))))) 
A( 0, A( 0, A( 0, A( 0, 5)))) 
A( 0, A( 0, A( 0, 6))) 
A( 0, A( 0, 7)) 
A( 0, 8) 

Result = 9

Leave a Reply