如何检测递归调用中的无限循环？

Question

我有一个递归调用自己的函数，我想检测并终止，如果进入一个无限循环，即 - 再次调用相同的问题。什么是最简单的方法来做到这一点？

编辑：这是函数，它将被递归调用x和y的不同值。如果在递归调用中，我想要终止对（x，y）的值。

int fromPos(int [] arr, int x, int y) 

Answer 1

如果功能纯粹是功能性的，也就是没有状态或副作用，那么你可以保留的参数的Set（编辑：看到你的编辑，你会保持一个集对的（X， y））它已被调用，并且每次只检查当前参数是否在集合中。这样，如果你很快遇到它，你可以检测到一个循环。但是如果参数空间很大并且需要很长时间才能重复，那么在检测到一个循环之前，可能会耗尽内存。一般来说，你不能这样做，因为这是停滞的问题。

Answer 2

的一种方法是从一个电话传递一个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; 
} 

Answer 3

一个简单的方法是执行下列操作之一：

以前的值和新的值传递给递归调用，让你的第一步检查，看他们是否相同 - 这可能是你的递归情况。

传递一个变量来表示该函数被调用的次数，并且任意限制它可以被调用的次数。

Answer 4

如果你想保留你的方法签名，你可以保留几组记录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); 
} 
} 

Answer 5

看起来你可能正在处理2D数组。如果你在数组的值中有多余的余数，你可以用它作为标志。检查它，如果标志已经设置，则终止递归。然后在继续之前设置它。

如果您在值中没有多余空间，您可以始终使其成为一个对象数组。

Answer 6

您只能使用程序分析来检测最不重要的程序。你所能做的最好的就是在你的特定情况下加入警卫，并通过深度级别的背景。检测一般情况并区分递归算法的合法使用几乎是不可能的。

Answer 7

您需要找到解决办法，因为正如您所问，没有通用的解决方案。有关更多信息，请参阅Halting problem。

Answer 8

您可以使用重载的一致的签名（这是更好的方法），也可以使用一个静态变量：

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; 
} 

约翰Kugelman与超载答案是更好的怎么一回事，因为它是线程安全的，而静态变量不是。

Billy3

Answer 9

恕我直言只有循环可以进入一个无限循环。

如果你的方法有太多的递归级别，JVM会抛出一个StackOverflowError。您可以使用try/catch块捕获此错误，并在出现此情况时执行您计划执行的任何操作。