简单循环Ackermann函数

Question

如何用简单的非递归循环编写Ackermann function？

Answer 1

这里是一个可能的实现：

import java.util.ArrayList; 

public class LinearAckermann { 

    static ArrayList<Long> mList = new ArrayList<Long>(); 

    public static long ackermann(long m, long n) { 
     while (true) { 
      if (m == 0) { 
       n += 1; 
       if (mList.isEmpty()) { 
        return n; 
       } else { 
        int index = mList.size() - 1; 
        m = mList.get(index); 
        mList.remove(index); 
       } 
      } else if (n == 0) { 
       m -= 1; 
       n = 1; 
      } else { 
       mList.add(m - 1); 
       n -= 1; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     System.out.println(ackermann(4, 1)); 
    } 
} 

它采用mList，而不是一个堆栈持有待审批工作;当堆栈变空时，它可以返回累计值。