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.