С кем поговорить о нерекурсивной функции Аккермана?

Question

Я написал нерекурсивное решение функции Ackermann, он работает отлично и работает быстрее, чем общее рекурсивное решение. Поэтому я смущен тем, почему это не примитивная рекурсивная функция, если она может быть решена итеративно? Мог ли кто-нибудь сказать мне, если я неправильно понял, что такое примитивные рекурсивные функции или с кем я должен поговорить об этом, чтобы получить ответ?

Ниже приведен код Java:

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 - переменная, которая не изменяется в корпусе контура. Чтобы получить функцию Аккермана, которая мажорирует все примитивно-рекурсивные функции, нужно добавить либо команду goto, либо неопределенные циклы, как ваш цикл while.