비 재귀 Ackermann 함수에 대해 이야기 할 대상은 누구입니까?

Question

Ackermann 함수에 비 재귀 적 솔루션을 작성했지만 완벽하게 작동하고 일반적인 재귀 솔루션보다 빠르게 작동하는 것 같습니다. 그래서 반복적으로 해결할 수 있다면 그것이 왜 원시적 인 재귀 함수가 아닌지 혼란 스럽습니다. 누군가가 원시적 인 재귀 함수가 무엇인지에 대해 오해했는지 또는 대답을 얻기 위해 내가 이것에 대해 누구에게 이야기해야하는지 말해 줄 수 있습니까?

다음은 자바 코드 :

import java.util.Scanner; 
import java.util.ArrayList; 

public class ackermann { 
    public static void main(String[] args){ 
     Scanner in = new Scanner(System.in); 

     System.out.println("Enter m:"); 
     int m = in.nextInt(); 

     System.out.println("Enter n:"); 
     int n = in.nextInt(); 

     ack(m, n); 
    } 

    public static void ack(int inM, int inN){ 
     if(inM < 0 || inN < 0) return; 

     ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>(); 

     for(int m = 0; m <= inM; m++){ 
      arr.add(new ArrayList<Integer>()); 
     } 

     Boolean done = false; 

     while(done == false){ 
      for(int m = 0; m <= inM; m++){ 
       int n = arr.get(m).size(); 
       int a = 0; 

       if(m == 0) a = n + 1; 
       else if(n == 0){ 
        if(arr.get(m - 1).size() <= 1) break; 
        a = arr.get(m - 1).get(1); 
       } else { 
        int k = arr.get(m).get(n - 1); 
        if(arr.get(m - 1).size() <= k) break; 
        a = arr.get(m - 1).get(k); 
       } 

       arr.get(m).add(a); 

       if(m == inM && n == inN){ 
        System.out.println("Ack(" + inM + ", " + inN + ") = " + a); 
        done = true; 
        break; 
       } 
      } 
     } 
    } 
} 

Answer 1

원시 재귀 함수 만 할당, + 및 명확한 루프를 사용하여 구현 될 수있다. 이 말은 다음 형식의 루프를 의미합니다.

for(int i = 0; i < n; i++) { ... } 

여기서 n은 루프 본문에서 변경되지 않은 변수입니다. 모든 원시적 인 재귀 함수를 주요하게 만드는 Ackermann의 함수를 얻으려면 goto 명령이나 while 루프와 같은 무한 루프를 추가해야합니다.