I have heard some novice programmers say "You can do anything with for-loops, so why bother using recursion at all?" To get rid of this misconception, we need to dig deep and discover the true secrets of recursion. Well there are some things in nature which are so fundamentally recursive that you can't do it with for loops at all. There are somethings which are so enormous and badly behaved that they had to be recursively defined. Well I guess most of us are familiar with the name Wilhelm Friedrich Ackermann. For those who haven't heard the name, he was a German mathematician who is remembered for his tremendous contributions in terms of theory of computation. It is his function that we are going to look at and hope to uncover some mysteries behind recursion. The test was, can you come up with something which just has to be totally recursively defined and you cannot by any way use for-loops (or any iterative methods) to make your way out. The studies which was done by Ackermann and other researchers made our conceptions somewhat clear about the behavior of functions which proved to be much beneficial in terms of identifying the nature of functions in general. Consider the hierarchy which was proposed by this famous mathematician.

Right in the bottom we can see the most simple ones, precisely the ones which can be de-recursed are Primitive Recursive. There is a whole layer above that called Recursive which are the functions where you have to use recursion. Just above this set of functions lies the all scary Recursively Enumerable Functions. To be clear, primitive recursions can be done with for loops and nested for loops, but you have a choice of using recursions also. Probably languages like Haskell prefers recursive techniques over the iterative ones. Above the level called Recursive ( where you have to define the problem recursively) lies the even more problematic set of functions called Recursively Enumerable functions. By Recursively Enumerable functions we mean that they are recursive but for some values that you put into the function, they will stop giving an answer and for others they will go on forever and they will never ever stop. Now how do you define 'forever'? Well forever and ever and ever they will go on repeating the same old stack frames and you won't even be aware of it. Now the question is " How can we define ahead of time for given arguments whether it will stop or won't?" . And the answer is Hello Alan Turing. In general that may well be undecidable which leads us to our next set of problems called "??Undecidable". So at the top of the hierarchy lies the great undecidable universe. There are some problems in computing which aren't decidable at all, not by any algorithm. Leaving aside the whole undecidable universe, let us go down to the more familier Recursive functions at level 2. Let's take a look at a recusrive function where I can reason through with you that it will give an answer. It cannot be considered as a part of the nasty Recursively Enumerable set where sometimes it would go wrong and keep spinning and not do anything useful. Here is a program written in C which can be used to calculate Ackermann's function.

#include <stdio.h>
int ack(m,n)
int m,n;
{
int ans;
if (m == 0) ans = n+1;
else if (n == 0) ans = ack(m-1,1);
else ans = ack(m-1, ack(m,n-1));
return (ans);
}

int main (argc, argv)
int argc; char ** argv;

{ int i,j;
for (i=0; i<6; i++)
for (j=0;j<6; j++)

printf ("ackerman (%d,%d) is: %d\n",i,j, ack(i,j));
}

We declare the recursive function as 'ack' for short .It is a function with two incoming integer arguments. It delivers back an integer result. It delivers the interger result in it local variable 'ans'. But how does it do its recursive horrors? If the incoming argument 'm' is zero, then deliver back the integer answer n+1. So if I came in with ack(0,2), because m = = 0 it will deliver back 3 as an answer. Easy, isn't it? Now, if that isn't true, else if n = = 0 then the answer is what you get by calleing up Ackermann recusrsively but this time by reducing m by 1 and with the second argument as 1 i.e ack(m-1,1). If you think that's not bad enough then here comes the next killer. If m isn't 0 and n isn't 0 then what's the genral case? The general case is the answer of ack(m-1,ack(m,n-1)). Notice that in the first argument we are reducing the value of m and the next argument is where your brain cries in pain. Think about the second argument more. It makes you realise why you can't de-recurse this by some iterative methods. The second argument for that generalised call of Ackermann is itself a call of Ackermann. So you have to go through endless, countless stackframes just to calculate what the second argument must be. Makes you just go through the same agony all over again. Here I would like to draw your attention to the fact that everytime m and n are altered in going around recursively, they reduce. Now when m and n is reduced to 0 and for that the traps that you have written i.e

if (m == 0) ans = n+1;
else if (n == 0) ans = ack(m-1,1);

then and only then the program will terminate. But one thing I would like to mention here is, if you really want an output ever (however long it might take to produce it) then you must feed in 0 or some positive integers as the arguments i.e 0<=m,0<=n. If you are willing to test this with negative integers then good luck for that. Let me know what happened. The most important thing here is, although the program will produce millions and millions of stackframes but because you are reducing the value of m and n, you can (with valid reasons of course) can convince yourself that eventually the program will terminate. Again, by saying this I am trying to highlight the fact that this problem is a regular recursion and not the recursively enumerable one.