Ackermann 함수를 재귀 적 스타일로 다시 작성하는 방법은 무엇입니까?

Question

나는 기능이

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

어떻게 비 재귀 스타일을 다시 작성해야? 아마도 구현 알고리즘입니까?

Answer 1

O (1)은 아니지만 확실히 재귀 적입니다.

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

이 숙제처럼 보이는, 그래서 나는 당신에게 대답을하지 않습니다하지만 올바른 방향으로 당신을 이끌 것입니다 : 당신이 밖으로 모두 나열 할

이 고장 재귀를 원하는 경우,이 유용 할 수 있습니다 진폭에 따라 m = {0 ... x} n = {0 ... y}가됩니다. 예를 들어

:이

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 

, 당신은 당신이 사용할 수있는 비 재귀 관계 (비 재귀 함수 정의)와 함께 올 수 있습니다.

편집 : 따라서이 숫자는 the Ackermann function이고 총 계산 가능한 함수는 이 아니며 프리미티브 재귀입니다.

Answer 3

이것은 본인이 이미 조사한 올바른 버전입니다.

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