Thread: Recursive Ackermann's function - need help

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.

Use iteration, i.e. loops. Can't help you right now cause I'm kinda busy. But if no one helps you by tomorrow, I'll help you then.

I need a valid response to this problem before 6:30 AM EST tomorrow.

Ooooo being a little pushy?

Nope, just procrastination at its best.

This function is *much* slower than O(n^3) I think it's like O(n^n).

It looks like you could maybe try to do a 2d
static array and then assign all the elements to 0. Then if a[m][n] != 0, a[m][n] = the computed value otherwise a[m][n] = the recursive definition.

Thank you, Nick! For that last algorithm. It really put me back on the right track.