如何以非递归方式重写Ackermann函数？
我有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)); } 如何以非递归方式重写它？ 也许，它实现了一些算法吗？
不完全是O（1）但绝对不是递归的。
public static int itFunc(int m, int n){ Stack s = new Stack ; 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; }
这看起来像是家庭作业，所以我不会给你答案，但我会引导你朝着正确的方向前进：
如果要分解递归，可能有助于在进展时列出所有值，让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函数 ，一个不是原始递归的总可计算函数。
这是我自己已经检查过的正确版本。
public static int Ackermann(int m, int n){ Stack s = new Stack ; 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 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(ox) && y.equals(oy);} } /** * @param args */ public static int ack_iter(int m, int n) { HashMap,Integer> solved_set= new HashMap,Integer>(120000); Stack> to_solve= new Stack>(); to_solve.push(new Pair(m,n)); while (!to_solve.isEmpty()) { Pair 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 next= new Pair (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 next0= new Pair(head.x, head.y-1); Integer result0= solved_set.get(next0); if(result0 == null) { to_solve.push(next0); } else { Pair next= new Pair(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(m,n)); } }