Skip to content

Instantly share code, notes, and snippets.

@nboubakr
Created November 21, 2014 20:44
Show Gist options
  • Save nboubakr/e63c25af093e175cacb2 to your computer and use it in GitHub Desktop.
Save nboubakr/e63c25af093e175cacb2 to your computer and use it in GitHub Desktop.
Ackermann Function: recursive and non recursive version
import java.util.Stack;
/**
*
* @author Boubakr
*/
public class Ackermann {
public static int RecursiveAckerman(int m, int n) {
if (m == 0) {
return (n + 1);
} else if (m > 0 && n == 0) {
return RecursiveAckerman(m - 1, 1);
} else {
return RecursiveAckerman(m - 1, RecursiveAckerman(m, n - 1));
}
}
public static int NonRecursiveAckerman(int m, int n) {
Stack<Integer> stack = new Stack<Integer>();
stack.add(m);
while (!stack.isEmpty()) {
m = stack.pop();
if (m == 0 || n == 0) {
n += m + 1;
} else {
stack.add(--m);
stack.add(++m);
n--;
}
}
return n;
}
public static void main(String[] args) {
System.out.println("RecursiveAckerman(1, 2) : " + RecursiveAckerman(1, 2));
System.out.println("NonRecursiveAckerman(1, 2): " + NonRecursiveAckerman(1, 2));
}
}
@Donnicias
Copy link

I changed this part } else if (m > 0 && n == 0) { to } else if (n == 0) { and it worked

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment