# Recursive Ackermann's function - need help

• 03-03-2002
Unregistered
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.
• 03-03-2002
golfinguy4
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.
• 03-03-2002
Unregistered
I need a valid response to this problem before 6:30 AM EST tomorrow.
• 03-03-2002
tim545666
Ooooo being a little pushy?
• 03-03-2002
Unregistered
Nope, just procrastination at its best. ;)
• 03-03-2002
Nick
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.
• 03-04-2002
Unregistered
Thank you, Nick! For that last algorithm. It really put me back on the right track.