CODEWITHSUNDEEP
pythonfunctionrecursion
Hummus
Hummus

Reputation: 365

Ackermann Function Understanding

I'm finding it difficult to understand how the Ackermann Function works. I think my understanding of recursion is flawed?

Here is the code in Python:

  def naive_ackermann(m, n):
    global calls
    calls += 1
    if m == 0:
        return n + 1
    elif n == 0:
        return naive_ackermann(m - 1, 1)
    else:
        return naive_ackermann(m - 1, naive_ackermann(m, n - 1))

If I do the function call of naive_ackermann(3,4), how and why do I end up getting 125?

Comments will be appreciated.

Thanks

Upvotes: 11

Views: 30518

Answers (4)

user7217035
user7217035

Reputation: 1

def ackermann(m,n):
    """computes the value of the Ackermann function for the input integers m and n.
       the Ackermann function being:
       A(m,n)=n+1               if m=0
             =A(m-1,1)          if m>0 and n=1
             =A(m-1,A(m,n-1)    if m>0 and n>0"""
    if m==0:
        print (n+1)
        return n+1
    elif m>0 and n==0:
        print ("ackermann(",m-1,",",1,")")                                          #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary
        return ackermann(m-1,1)
    elif m>0 and n>0:
        print ("Ackermann(",m-1,",","Ackermann(",m,",",n-1,")",")")                  #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary
        return ackermann(m-1,ackermann(m,n-1))

Just make a simple modification to your code so that the program prints every steps rather than just the result. The code should look somewhat like what's at the end of this page. Run it, (might take a few seconds) and then you can appreciate how an Ackermann function is computed.

Upvotes: 0

Abhranil Das
Abhranil Das

Reputation: 5918

The computation of A(3,4) is not as easy or short as it might appear at first from the small values of the arguments. The complexity (# of iteration steps) of the Ackermann function grows very rapidly with its arguments, as does the computed result.

Here is the definition of the Ackermann function from Wikipedia:

enter image description here

As you can see, at every iteration, the value of m decreases until it reaches 0 in what will be the last step, at which point the final value of n (+1) gives you the answer. So for the answer, you only need to trace how n changes as you go through the recursive iterations. For why the Ackermann function grows so rapidly, you can take a look at this subsection of the wiki.

As Joran Beasley has already mentioned, A(3,4) is indeed 125, as written in Wikipedia. However, the process to get to this result is not very short. In fact, as I found out, it is required to compute by recursion 315 Ackermann function values to get A(3,4), the number of iterations required being roughly proportional to that.

If you still wish to visualize how this result is arrived at, you can take a look at this page, which animates the calculation of every recursion step. Be warned, though, that A(3,4) will take forever to finish animating here, but at least you might get some idea of the process with smaller arguments.

Upvotes: 16

Janne Karila
Janne Karila

Reputation: 25197

Here's a version that prints an explanation:

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 A(2,2)

With arguments 2,2 the output is this. (With 3,4 it becomes already a bit too much)

A(2,2)
A(1,A(2,1))
A(1,A(1,A(2,0)))
A(1,A(1,A(1,1)))
A(1,A(1,A(0,A(1,0))))
A(1,A(1,A(0,A(0,1))))
A(1,A(1,A(0,2)))
A(1,A(1,3))
A(1,A(0,A(1,2)))
A(1,A(0,A(0,A(1,1))))
A(1,A(0,A(0,A(0,A(1,0)))))
A(1,A(0,A(0,A(0,A(0,1)))))
A(1,A(0,A(0,A(0,2))))
A(1,A(0,A(0,3)))
A(1,A(0,4))
A(1,5)
A(0,A(1,4))
A(0,A(0,A(1,3)))
A(0,A(0,A(0,A(1,2))))
A(0,A(0,A(0,A(0,A(1,1)))))
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,1))))))
A(0,A(0,A(0,A(0,A(0,2)))))
A(0,A(0,A(0,A(0,3))))
A(0,A(0,A(0,4)))
A(0,A(0,5))
A(0,6)
7

Upvotes: 9

Joran Beasley
Joran Beasley

Reputation: 113988

ackerman(3,4) 

=ackerman(2,ackerman(3,3)) = ackerman(2,61)    #ackerman(3,3) = 61 ...
=ackerman(1,ackerman(2,60)) = ackerman (1,123)  #ackerman(2,60) = 123...
=ackerman(0,ackerman(1,122)) = ackerman (0,124)  #ackerman(1,122) = 124...
= 124+1 = 125

see http://goo.gl/jDDEA here to visualize ackerman(2,3) ( It was too long to visualize 3,4)

Upvotes: 3

Related Questions