1. 题目描述
/**
阿克曼(Ackmann)函数 【题目描述】
阿克曼(Ackmann)函数A(m，n)中，m，n定义域是非负整数(m<=3,n<=10)，函数值定义为：
akm(m,n) = n+1; (m=0时)
akm(m,n) = akm(m-1,1); (m>0,n=0时)
akm(m,n) = akm(m-1,akm(m, n-1)); （m,n>0时) 【输入】输入m和n。 【输出】函数值。 【输入样例】2 3
【输出样例】9
*/
写出递归与非递归算法，并输出调用过程。
2. 代码实现递归和非递归
import java.util.Stack;
public class Main2 {
public static void main( String[] args ) {
System.out.println(AkmRecur(2, 3));
System.out.println(AkmNonRecur(2, 3));
}
//递归
public static int AkmRecur(int m, int n) {
if (m == 0)
return n + 1;
else if (n == 0)
return AkmRecur(m - 1, 1);
else
return AkmRecur(m - 1, AkmRecur(m, n - 1));
}
//非递归
public static int AkmNonRecur(int m, int n) {
Stack<Integer> sx = new Stack<Integer>();
Stack<Integer> sy = new Stack<Integer>();
int x = 0;
int y = 0;
sx.push(m);
sy.push(n);
while ((!sx.empty()) && (!sy.empty())) {
if (sx.peek() != 0 && sy.peek() == 0) {// m!=0 n==0
x = sx.peek();
y = sy.peek();
sx.pop();
sy.pop();
sx.push(x-1);
sy.push(1);
}else if (sx.peek() != 0 && sy.peek() != 0) {// m!=0 n!=0
while (sx.peek()!= 0 &&sy.peek()!= 0) {
x = sx.peek();
y = sy.peek()-1;
sx.pop();
sy.pop();
sx.push(x-1);
sy.push(-1);//如果m！=0&&n!=0, n暂时存放-1,代表是一个整体
sx.push(x);
sy.push(y);
}
} else {// m==0
y = sy.peek();
sx.pop();
if (sx.empty()){
return y + 1;
} else {
sy.pop();//弹出 y
sy.pop();//弹出-1
sy.push(y+1);
}
}
}
return -1;
}
}