# ackermann function

• 08-17-2008
misterMatt
ackermann function
Is my implementation correct? I'm assuming it's not because I keep getting zero returned... Where am I going wrong?
Code:

```//implementation of the recursive ackermann function int ack(int m, int n) {     if (m == 0){         return n+1;     }     else if(m > 0){         ack(m-1, 1);     }     else if((m > 0) && (n > 0)){         ack(m-1, ack(m, n-1));     } }//end ack```
• 08-17-2008
Kernel Sanders
The third condition is never used. If m>0 the second will be evaluated whether n>0 or not. You also need to return ack(whatever) instead of just invoking it. As is the value is never used or returned, just computed and thrown out
• 08-17-2008
misterMatt
Quote:

Originally Posted by Kernel Sanders
The third condition is never used. If m>0 the second will be evaluated whether n>0 or not. You also need to return ack(whatever) instead of just invoking it. As is the value is never used or returned, just computed and thrown out

My mistake on the missing return bit. I'm not sure why I overlooked that... Anyway, I've updated the conditions of the second else if - they should now properly match the wikipedia entry.

Code:

```//implementation of the recursive ackerman function int ack(int m, int n) {     if (m == 0){         return n+1;     }     else if((m > 0) && (n == 0)){         return ack(m-1, 1);     }     else if((m > 0) && (n > 0)){         return ack(m-1, ack(m, n-1));     } }//end ack```
• 08-18-2008
misterMatt
A quick question about the above, however. The book I'm working through suggested I implement the function to learn about recursion. The book also stated that this is a popular demonstration of recursion that is commonly used in CS courses all over the place.

anyway, my question is: What exactly is the point of the function? What purpose does it serve? The wikipedia page turned out to be a little too 'mathematically verbose'.
• 08-18-2008
CornedBee
The ackermann function has no practical purpose.

It's importance lies in mathematical theory. There are several formalisms that are important to decide on the computability of a function. Nowadays the most important of those are the Turing machine and lambda calculus. It is said that if a function can be expressed as a Turing machine or in lambda calculus, it is computable.
Before those were developed, however, there was a different formalism. This formalism defined the set of what is now known as "primitive recursive functions". At the time, it was theorized that this formalism was sufficient for describing all computable functions.
The ackermann function is a counterexample for this. While it is computable, it cannot be expressed using the old formalism. Thus its importance in theoretical mathematics: it forced people to come up with new formalisms. (They found &#181;-recursion, Turing machines and lambda calculus, all of which were later proven to be equivalent in expressiveness.)