Hello everyone. I'm new to this board. Just discovered it a short while ago while searching for help on homework. Was wondering if anybody here could help me.

I need to write a recursive version of the Ackermann function/algorithm, which is:

Ackermann(m,n) = { n+1 if m=0

Ackermann(m-1, 1) if n = 0

otherwise Ackermann(m-1), Ackermann(m, n-1))

Now a direction coding of this function would be:

int ackermann(int m, int n){

if (m == 0) return n + 1;

if (n == 0) return ackermann(m - 1, 1);

return ackermann(m - 1, ackermann(m, n -1));

}

But this function is probably somewhere along the lines of O^3 as far as Big O is concerned. Which basically means any number halfway to 10 called by the function would take a lot of time. Forget double digit numbers. I need a more efficient version of function.

What I have in mind is something that involves Dynamic Programming. Making a table through matrix and then storing already calculated integers in that table and then calling them whenever they come up when the function is checking for a base case. This would GREATLY increase the speed. So I have in mind, a for loop with the table. Anybody who could gimme a hand with this, I would greatly appreciate it. Thank you.