如何检测无限循环在递归的电话？

StackOverflow https://stackoverflow.com/questions/1030527

  •  06-07-2019
  •  | 
  •  

题

我有个功能是递归的呼吁本身，我想要检测和终止，如果进入一个无限循环下，我.e-得到呼吁同样的问题。什么是简单的方法来做到这一点?

编辑：这是功能，并且它将得到称为递归具有不同价值观的x和y。我想要终止，如果在一个递归的呼吁，值对(x,y)重复。 

int fromPos(int [] arr, int x, int y)
有帮助吗？

解决方案

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

其他提示

一种方法是将 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;
}

您需要找到一种解决方法，因为正如您所问，它没有通用解决方案。有关详细信息，请参阅暂停问题。

一种简单的方法是实现以下之一：

将先前的值和新值传递给递归调用，并检查第一步是否相同 - 这可能是您的递归情况。

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

您只能使用程序分析检测最简单的那些。您可以做的最好的事情是在您的特定环境中添加警卫并传递深度级别背景。几乎不可能检测到一般情况并区分递归算法的合法使用。

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

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对重载的回答更好，因为它的线程安全，而静态变量不是。

Billy3

看起来您可能正在处理2D阵列。如果您在数组的值中有一些额外的位，则可以将其用作标志。检查它，如果已设置标志，则终止递归。然后在继续之前设置它。

如果你没有多余的值，你总是可以把它变成一个对象数组。

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

IMHO只有循环可以进入无限循环。

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

递归功能终止情况下的一个条件被满足。

实例：

  • 结果的一个函数 0 或是 1
  • 最大数量的电话是达成了
  • 其结果是低于/高于输入的价值

在你的情况的条件是 ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])

0, 1, ...N 是索引的对

因此你需要一个容器(矢量、列表、地图)储存的所有先前对和比较他们目前对。

首先使用mvn findbugs：gui打开gui，指向存在此错误的行。

我也面临同样的问题，我通过在循环验证中添加一个布尔变量来解决它。

之前的代码 - ＆gt; 

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

要解决这个问题，我刚刚添加了一个布尔变量，并在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;
            }
          }

这就是我解决这个问题的方法。 希望这会有所帮助。 ：）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top