I have function
public static int func(int M,int N){
if(M == 0 || N == 0) return M+N+1;
return func(M-1, func(M, N-1));
}
How to rewrite it in non-recursive style ? Maybe, is it implementation some algorithm?
I have function
public static int func(int M,int N){
if(M == 0 || N == 0) return M+N+1;
return func(M-1, func(M, N-1));
}
How to rewrite it in non-recursive style ? Maybe, is it implementation some algorithm?
This is the a correct version which already examined by myself.
I couldn't get @LightyearBuzz's answer to work, but I found this Java 5 code from WikiWikiWeb that worked for me:
Not quite O(1) but definitely non-recursive.
This looks like homework, so I won't give you the answer but I will lead you in the right direction:
If you want to breakdown the recursion, it might be useful for you to list out all the values as they progress, letting m = {0...x} n = {0...y}.
For example:
With this, you can come up with a non-recursive relationship (a non-recursive function definition) that you can use.
Edit: So it looks like this is the Ackermann function, a total computable function that is not primitive recursive.