java 如何检测递归调用中的无限循环？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1030527/
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
How to detect an infinite loop in a recursive call?
提问by Pranav
I have a function that is recursively calling itself, and i want to detect and terminate if goes into an infinite loop, i.e - getting called for the same problem again. What is the easiest way to do that?
我有一个递归调用自身的函数，我想检测并终止是否进入无限循环，即 - 再次被调用以解决相同的问题。最简单的方法是什么？
EDIT: This is the function, and it will get called recursively with different values of x and y. i want to terminate if in a recursive call, the value of the pair (x,y) is repeated.
编辑：这是函数，它将以不同的 x 和 y 值递归调用。如果在递归调用中重复 (x,y) 对的值，我想终止。
int fromPos(int [] arr, int x, int y)
回答by John Kugelman
One way is to pass a depthvariable from one call to the next, incrementing it each time your function calls itself. Check that depthdoesn't grow larger than some particular threshold. Example:
一种方法是将depth变量从一次调用传递到下一次调用，每次函数调用自身时都会增加它。检查depth是否增长不超过某个特定阈值。例子：
int fromPos(int [] arr, int x, int y)
{
return fromPos(arr, x, y, 0);
}
int fromPos(int [] arr, int x, int y, int depth)
{
assert(depth < 10000);
// Do stuff
if (condition)
return fromPos(arr, x+1, y+1, depth + 1);
else
return 0;
}
回答by newacct
If the function is purely functional, i.e. it has no state or side effects, then you could keep a Setof the arguments (edit: seeing your edit, you would keep a Set of pairs of (x,y) ) that it has been called with, and every time just check if the current argument is in the set. That way, you can detect a cycle if you run into it pretty quickly. But if the argument space is big and it takes a long time to get to a repeat, you may run out of your memory before you detect a cycle. In general, of course, you can't do it because this is the halting problem.
如果该函数是纯函数式的，即它没有状态或副作用，那么您可以保留一个Set已被调用的参数（编辑：查看您的编辑，您将保留一组 (x,y) 对） with, 并且每次只检查当前参数是否在集合中。这样，如果您很快遇到循环，就可以检测到它。但是，如果参数空间很大并且需要很长时间才能重复，则可能会在检测到循环之前耗尽内存。一般来说，当然，你不能这样做，因为这是停机问题。
回答by JP Alioto
You will need to find a work-around, because as you've asked it, there is no general solution. See the Halting problemfor more info.
您需要找到一种解决方法，因为正如您所问的那样，没有通用的解决方案。有关更多信息，请参阅暂停问题。
回答by Relster
An easy way would be to implement one of the following:
一种简单的方法是实施以下其中一项：
Pass the previous value and the new value to the recursive call and make your first step a check to see if they're the same - this is possibly your recursive case.
将先前的值和新值传递给递归调用，并检查它们是否相同 - 这可能是您的递归情况。
Pass a variable to indicate the number of times the function has been called, and arbitrarily limit the number of times it can be called.
传递一个变量来表示函数被调用的次数，任意限制可以调用的次数。
回答by ojblass
You can only detect the most trivial ones using program analysis. The best you can do is to add guards in your particular circumstance and pass a depth level context. It is nearly impossible to detect the general case and differentiate legitimate use of recursive algorithms.
您只能使用程序分析检测最琐碎的。您能做的最好的事情是在您的特定情况下添加守卫并传递深度级别的上下文。检测一般情况并区分递归算法的合法使用几乎是不可能的。
回答by Billy ONeal
You can either use overloading for a consistent signature (this is the better method), or you can use a static variable:
您可以使用重载来获得一致的签名（这是更好的方法），也可以使用静态变量：
int someFunc(int foo)
{
static recursionDepth = 0;
recursionDepth++;
if (recursionDepth > 10000)
{
recurisonDepth = 0;
return -1;
}
if (foo < 1000)
someFunc(foo + 3);
recursionDepth = 0;
return foo;
}
John Kugelman's answer with overloading is better beacuse it's thread safe, while static variables are not.
John Kugelman 对重载的回答更好，因为它是线程安全的，而静态变量不是。
Billy3
比利3
回答by Peter Lawrey
IMHO Only loops can go into an infinite loop.
恕我直言，只有循环才能进入无限循环。
If your method has too many level of recursion the JVM will throw a StackOverflowError. You can trap this error with a try/catch block and do whatever you plan to do when this condition occurs.
如果您的方法具有太多递归级别，JVM 将抛出 StackOverflowError。您可以使用 try/catch 块捕获此错误，并在出现此情况时执行您计划执行的任何操作。
回答by Th. Thielemann
A recursive function terminates in case a condition is fulfilled.
递归函数在满足条件的情况下终止。
Examples:
例子：
- The result of a function is
0or is1 - The maximum number of calls is reached
- The result is lower/greater than the input value
- 函数的结果是
0或是1 - 达到最大调用次数
- 结果小于/大于输入值
In your case the condition is ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])
在你的情况下，条件是 ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])
0, 1, ...Nare the indexes of the pairs
0, 1, ...N是对的索引
Thus you need a container(vector, list, map) to store all previous pairs and compare them to the current pair.
因此，您需要一个容器（向量、列表、地图）来存储所有以前的对并将它们与当前对进行比较。
回答by AKASH DUBEY
First use mvn findbugs:gui to open a gui which point to the line where this error is present.
首先使用 mvn findbugs:gui 打开一个 gui，它指向出现此错误的行。
I also faced the same problem and I solved it by adding a boolean variable in the loop verification.
我也遇到了同样的问题，我通过在循环验证中添加一个布尔变量来解决它。
Code before ->
之前的代码 ->
for (local = 0; local < heightOfDiv; local = local + 200) { // Line under Error
tileInfo = appender.append(tileInfo).append(local).toString();
while (true) {
try {
tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
incr++;
} catch (Exception e) {
incr = 1;
tileInfo = appender.append(tileInfo).append("/n").toString();
}
}
To Solve this problem, I just added a boolean variable and set it to false in the catch block. Check it down
为了解决这个问题，我只是添加了一个布尔变量，并在 catch 块中将其设置为 false。检查下来
for (local = 0; local < heightOfDiv; local = local + 200) {
tileInfo = appender.append(tileInfo).append(local).toString();
boolean terminationStatus = true;
while (terminationStatus) {
try {
tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
incr++;
} catch (Exception e) {
incr = 1;
tileInfo = appender.append(tileInfo).append("/n").toString();
terminationStatus = false;
}
}
This is how i Solved this problem. Hope this will help. :)
这就是我解决这个问题的方法。希望这会有所帮助。:)
回答by Tom
If you want to keep your method signature, you could keep a couple of sets to record old values of x and y.
如果你想保留你的方法签名，你可以保留几个集合来记录 x 和 y 的旧值。
static Set<Integer> xs;
static Set<Integer> ys;//Initialize this!
static int n=0;//keeps the count function calls.
int fromPos(int [] arr, int x, int y){
int newX= getX(x);
int newY= getY(y);
n++;
if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){
assert(n<threshold); //threshold defined elsewhere.
fromPos(arr,newx,newy);
}
}
