Wie kann man die Ackermann-Funktion in nicht-rekursivem Stil umschreiben?

Question

Ich habe Funktion

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)); 
} 

Wie es in nicht-rekursive Stil neu zu schreiben? Vielleicht ist es die Implementierung eines Algorithmus?

Answer 1

Nicht ganz O (1), aber definitiv nicht rekursiv.

public static int itFunc(int m, int n){ 
    Stack<Integer> s = new Stack<Integer>; 
    s.add(m); 
    while(!s.isEmpty()){ 
     m=s.pop(); 
     if(m==0||n==0) 
      n+=m+1; 
     else{ 
      s.add(--m); 
      s.add(++m); 
      n--; 
     } 
    } 
    return n; 
} 

Answer 2

Das sieht aus wie Hausaufgaben, so dass ich Ihnen keine Antwort geben, aber ich werde dich in die richtige Richtung führen:

Wenn Sie die Rekursion Zusammenbruch wollen, könnte es sinnvoll sein, für Sie alles aufzulisten die Werte, während sie fortschreiten, wobei m = {0 ... x} n = {0 ... y}.

Zum Beispiel:

m = 0, n = 0 = f(0,0) = M+N+1 = 1 
m = 1, n = 0 = f(1,0) = M+N+1 = 2 
m = 1, n = 1 = f(1,1) = f(0,f(1,0)) = f(0,2) = 3 
m = 2, n = 1 = f(2,1) = f(1,f(2,0)) = f(1,3) = f(0,f(1,2)) = f(0,f(0,f(1,1)) 
      = f(0,f(0,3))   = f(0,4) = 5 

Mit diesem können Sie mit einer nicht-rekursive Beziehung kommen (eine nicht-rekursive Funktionsdefinition), die Sie verwenden können.

Edit: So sieht es aus wie the Ackermann function, eine insgesamt berechenbare Funktion, die nicht primitive rekursive ist.

Answer 3

Dies ist eine richtige Version, die bereits von mir untersucht.

public static int Ackermann(int m, int n){ 
Stack<Integer> s = new Stack<Integer>; 
s.add(m); 
while(!s.isEmpty()){ 
    m=s.pop(); 
    if(m==0) { n+=m+1; } 
    else if(n==0) 
    { 
     n += 1; 
     s.add(--m); 
    } 
    else{ 
     s.add(--m); 
     s.add(++m); 
     n--; 
    } 
} 
return n; 
}