8

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

编辑：这是函数，它将以不同的 x 和 y 值递归调用。如果在递归调用中，我想终止对 (x,y) 的值重复。

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

11 回答 11

20

一种方法是将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;
}
于 2009-06-23T03:45:55.923 回答
11

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

于 2009-06-23T03:56:43.343 回答
4

您将需要找到一种解决方法，因为正如您所要求的那样，没有通用的解决方案。有关更多信息，请参阅停止问题。

于 2009-06-23T04:01:53.373 回答
2

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

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

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

于 2009-06-23T03:47:50.867 回答
2

您只能使用程序分析来检测最微不足道的那些。您可以做的最好的事情是在您的特定情况下添加警卫并传递深度级别的上下文。检测一般情况并区分递归算法的合法使用几乎是不可能的。

于 2009-06-23T04:00:58.490 回答
1

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

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

比利3

于 2009-06-23T04:05:31.750 回答
0

如果你想保留你的方法签名，你可以保留几组来记录 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);
 }
}
于 2009-06-23T03:54:29.960 回答
0

看起来您可能正在处理二维数组。如果您在数组的值中有多余的空余部分，则可以将其用作标志。检查它，如果标志已设置，则终止递归。然后在继续之前设置它。

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

于 2009-06-23T03:59:27.947 回答
0

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

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

于 2009-06-23T05:56:51.673 回答
0

递归函数在满足条件时终止。

例子：

  • 函数的结果是0或是1
  • 已达到最大调用次数
  • 结果小于/大于输入值

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

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

因此，您需要一个容器（向量、列表、地图）来存储所有先前的对并将它们与当前对进行比较。

于 2018-05-15T10:50:16.320 回答
0

首先使用 mvn findbugs:gui 打开一个 gui，它指向出现此错误的行。

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

之前的代码->

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

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

于 2018-11-20T14:03:17.657 回答