How to rewrite Ackermann function in non-recursive style?

Question

I have function

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

How to rewrite it in non-recursive style ? Maybe, is it implementation some algorithm?

Answer 1

Not quite O(1) but definitely non-recursive.

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

All the answers posted previously don't properly implement Ackermann.

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

This looks like homework, so I won't give you the answer but I will lead you in the right direction:

If you want to breakdown the recursion, it might be useful for you to list out all the values as they progress, letting m = {0...x} n = {0...y}.

For example:

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

With this, you can come up with a non-recursive relationship (a non-recursive function definition) that you can use.

Edit: So it looks like this is the Ackermann function, a total computable function that is not primitive recursive.

Answer 4

This is the a correct version which already examined by myself.

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

Answer 5

I couldn't get @LightyearBuzz's answer to work, but I found this Java 5 code from WikiWikiWeb that worked for me:

import java.util.HashMap;
import java.util.Stack;

public class Ackerman {
  static class  Pair <T1,T2>{
    T1 x; T2 y;
    Pair(T1 x_,T2 y_) {x=x_; y=y_;}
    public int hashCode() {return x.hashCode() ^ y.hashCode();}
    public boolean equals(Object o_) {Pair o= (Pair) o_; return x.equals(o.x) && y.equals(o.y);}
  }

  /**
   * @param args
   */
  public static int ack_iter(int m, int n) {
    HashMap<Pair<Integer,Integer>,Integer> solved_set= new HashMap<Pair<Integer,Integer>,Integer>(120000);
    Stack<Pair<Integer,Integer>> to_solve= new Stack<Pair<Integer,Integer>>();
    to_solve.push(new Pair<Integer,Integer>(m,n));

    while (!to_solve.isEmpty()) {
      Pair<Integer,Integer> head= to_solve.peek();
      if (head.x.equals(0) ) {
        solved_set.put(head,head.y + 1);
        to_solve.pop();
      }
      else if (head.y.equals(0)) {
        Pair<Integer,Integer> next= new Pair<Integer,Integer> (head.x-1,1);
        Integer result= solved_set.get(next);
        if(result==null){
          to_solve.push(next);
        } 
        else {
          solved_set.put(head, result);
          to_solve.pop();
        }
      }
      else {
        Pair<Integer,Integer> next0= new Pair<Integer,Integer>(head.x, head.y-1);
        Integer result0= solved_set.get(next0);
        if(result0 == null) {
          to_solve.push(next0);
        }
        else {
          Pair<Integer,Integer> next= new Pair<Integer,Integer>(head.x-1,result0);
          Integer result= solved_set.get(next);
          if (result == null) {
            to_solve.push(next);
          }
          else {
            solved_set.put(head,result);
            to_solve.pop();
          }
        }
      }
    }
    System.out.println("hash size: "+solved_set.size());
    System.out.println("consumed heap: "+ (Runtime.getRuntime().totalMemory()/(1024*1024)) + "m");
    return solved_set.get(new Pair<Integer,Integer>(m,n));
  }
}

Answer 6

Written in python, using only 1 array and 1 variable, hope this helps!

def acker(m,n):

    right = [m]
    result = n
    i = 0

    while True:
        if len(right) == 0:
            break

        if right[i] > 0 and result > 0:
            right.append(right[i])
            right[i] -= 1
            result -= 1
            i += 1

        elif right[i] > 0 and result == 0:
            right[i] -= 1
            result = 1

        elif right[i] == 0:
            result += 1
            right.pop()
            i -=1

    return result

Answer 7

Well I came here to find the answer of this question. But could not write a code even after looking at the answers. So, I tried it myself and after some struggle built the code. So, I will give you a hint (because I feel etiquettes here are that the homework questions are not meant to be fully answered). So you can use a single stack to compute the function without using recursion. Just look at the flow of control in David's answer. You have to use that. Just start a while(1) loop and inside that check for the case your arguments are satisfying. Let the desired block amongst if-else blocks execute.Then push the two latest arguments of ackerman function into the stack. Then at the end of the loop pop them and let the cycle repeat till an end condition is reached where no further arguments of ackermann function are generated. You have to put a for statement inside the while loop to keep checking it. And finally get the final results. I don't know how much of this is understandable, but I wish I could have some idea to start with. So, just shared the way.

Answer 8

Written using C++. Stack stores only m values and works fine for all inputs

int ackermann(int m, int n) {
    stack<int> s;
    s.push(m);
    while(!s.empty()) {
        m = s.top();
        s.pop();
        if(m == 0) {
            n++;
        }
        else if(n == 0) {
            s.push(--m);
            n = 1;
        }
        else {
            s.push(m-1);
            s.push(m);
            n--;
        }
    }
    return n;
}