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

One response to “Implementation of Ackermann Function in Python”

  1. Shreejan Shrestha says:

    I was doing this in my copy…
    Imagine level of my patience. The moment I thought “yes!!! I got this”, another recursion with 3rd condition starts. LOL But major task here counting how many recursive function the function called from beginning to end. Now start to count hahahahaha

Leave a Reply

Your email address will not be published. Required fields are marked *