如何以非递归方式重写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

之前发布的所有答案都没有正确实施阿克曼。

def acker_mstack(m, n)
  stack = [m]
  until stack.empty?
    m = stack.pop

    if m.zero?
      n += 1
    elsif n.zero?
      stack << m - 1
      n = 1
    else
      stack << m - 1 << m
      n -= 1
    end
  end
  n
end

Answer 3

这看起来像是家庭作业,所以我不会给你答案,但我会引导你朝着正确的方向前进:

如果要分解递归,可能有用的是在进展时列出所有值,让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

有了这个,您可以提出一个可以使用的非递归关系(非递归函数定义).

编辑:所以看起来这是Ackermann函数,一个不是原始递归的总可计算函数.