I 有函数
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));
}
如何以非递归风格重写它？也许，是实现某种算法吗？
不完全是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;
}
之前发布的所有答案都没有正确实现 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
这看起来像家庭作业，所以我不会给你答案，但我会引导你朝着正确的方向前进：
如果要分解递归，列出所有值可能会很有用，让 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
有了这个，你可以想出一个你可以使用的非递归关系（一个非递归函数定义）。
编辑：所以看起来这是阿克曼函数，一个完全可计算的函数，不是原始递归的。
这是我
自己已经检查过的正确版本。
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;
}
我无法得到@LightyearBuzz的答案，但我从WikiWikiWeb中找到了这个对我有用的Java 5代码：
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));
}
}
用 python 编写，仅使用 1 个数组和 1 个变量，希望这有帮助！
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
好吧，
我来这里是为了找到这个问题的答案。但即使看了答案也无法编写代码。所以，我自己尝试了一下，经过一番挣扎，构建了代码。所以，我会给你一个提示（因为我觉得这里的礼节是家庭作业问题并不意味着要完全回答）。因此，您可以使用单个堆栈来计算函数，而无需使用递归。看看大卫回答中的控制流程就知道了。你必须使用它。只需启动一个 while（1） 循环，然后在其中检查您的参数是否满足的情况。让 if-else 块中的所需块执行。然后将 ackerman 函数的两个最新参数推送到堆栈中。然后在循环结束时弹出它们，让循环重复，直到达到结束条件，不再生成阿克曼函数的参数。您必须在 while 循环中放置一个 for 语句才能继续检查它。并最终得到最终结果。我不知道这其中有多少是可以理解的，但我希望我能有一些想法开始。所以，只是分享了方式。
使用 C++ 编写。堆栈仅存储 m 值，适用于所有输入
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;
}