java 学习Java递归，阿克曼函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1628756/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Learning Java Recursion, Ackerman function
提问by Benzle
I'm working on a recursive Ackermannfunction in Java. I am getting an error at may recursive line, 23.
我正在研究Java 中的递归Ackermann函数。我在 May 递归行 23 处遇到错误。
return Ack(m - 1, Ack(m, n - 1));
return Ack(m - 1, Ack(m, n - 1));
Thanks so much if anyone could point out what's wrong.
非常感谢，如果有人能指出什么是错的。
-Kyle
-凯尔
/*enter code here
Ackerman's function, A(m, n) is defined:
A(0 , n) = n + 1 for n >= 0
A(m , 0) = A(m – 1 , 1) for m > 0
A(m , n) = A(m – 1 , A(m , n - 1)) for n >= 0
*/
public class AckFun {
public static int Ack(int m, int n) {
if (m == 0) {
return 2 * n;
} else if (m >= 1) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 2;
} else {
return Ack(m - 1, Ack(m, n - 1));
}
}
return n; // Not sure what to return here, Eclipse suggested this.
}
public static void main(String args[]) {
System.out.println(Ack(3, 4));
}
}
回答by Denis Tulskiy
You need to make your stack larger:
你需要让你的堆栈更大：
http://thilinamb.wordpress.com/2008/12/22/how-to-increase-the-java-stack-size/
http://thilinamb.wordpress.com/2008/12/22/how-to-increase-the-java-stack-size/
With larger stack it runs without stackoverflow, but gives 0.
使用更大的堆栈，它在没有 stackoverflow 的情况下运行，但给出 0。
EDIT: Your code is wrong, that is why it gives the error. Try to rewrite the code exactly as the definition says:
编辑：您的代码是错误的，这就是它给出错误的原因。尝试完全按照定义重写代码：
//I assume that you check that n and m are non-negative before you run this
if (m == 0) {
return n + 1;
} else if (n == 0) {
return Ack(m - 1, 1);
} else {
return Ack(m - 1, Ack(m, n - 1));
}
PS. Don't blame me for posting source code for homework problems. I believe that the best way to learn programming is by reading and understanding someone else's code.
附注。不要怪我发布了家庭作业问题的源代码。我相信学习编程的最好方法是阅读和理解别人的代码。
回答by Josh Lee
You've exceeded the maximum recursion depth. That's one of the features of the Ackermann function. :)
您已超出最大递归深度。这是阿克曼函数的特征之一。:)
If you call it with smaller numbers, like Ack(3,3), then it doesn't overflow the stack.
如果你用更小的数字调用它，比如Ack(3,3)，那么它不会溢出堆栈。
It's possible to increase Java's recursion depth limit, but that's not necessarily a good solution. This may be an exercise in transforming the program so that it doesn't use Java's built-in call stack, but keeps track of each call in a data structure (perhaps a Stack). You can also use memoization, where you record the result of the function call so you don't have to compute the same result over and over.
可以增加 Java 的递归深度限制，但这不一定是一个好的解决方案。这可能是转换程序的练习，以便它不使用 Java 的内置调用堆栈，而是跟踪数据结构（可能是堆栈）中的每个调用。您还可以使用记忆功能，在其中记录函数调用的结果，这样您就不必一遍又一遍地计算相同的结果。
回答by user unknown
With a return in front, you don't need 'else'.
前面有 return，你不需要'else'。
if (m == 0) return n + 1;
if (n == 0) return ack (m - 1, 1);
return ack (m - 1, ack (m, n - 1));
