ACKERMANN RECURSION MYSTERY

RECURSION   is one of the beautiful techniques of programming. Instead of repeating the whole code, several programmers are using this technique in their programs. But using recursion is not a good programming methods, since it will consume memory space and other resources. There are large number of problems in computer science which depends upon the recursion for their result. Some of them are Fibanocci numbers, Factorial, Towers of Hanoi problem, N-queens problem, DFS,BFS, most of the tree and graph related problems etc.

ACKERMANN function is a problem which works using the principles of recursion, especially tail recursion. The peculiarity of the function is that the output will be obtained for the small values very rapidly and if the input values exceed one particular number then the function behaves like an algorithm which never comes up with the answer. The tracing of the function for small values can be done with ease effort. The function is described as follows

                                              A(m,n) =   n + 1 ,                         if    m=0;
                                                            =   A(m-1,1),                  if    n=0;
                                                            =   A(m-1, A(m, n-1))   otherwise;


The values m and n must be greater than or equal to zero. If we execute this program with the values A(3,2) we will get 29. similarly if A(3,3) we will get 61. If we go beyond 4 or 5 it will take large amount of time, Sometimes years!!!!!!!!!!!!!. In that condition the complexity of the program as explained in some books looks like


                                                               .....
                                                             .... 
                                                           2
                                                         2
                                                       2


A slope of 2's arranged one above the other..

Ackermanns function is a typical example of tail recursion.. Some people may say as a joke that running complex recursive algorithms are worth enough  for giving training to the processors...