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

Question

我有一个递归调用自身的函数，我想检测并终止它是否进入无限循环，也就是说，再次为同一个问题被调用。最简单的方法是什么

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

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

Answer 1

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

一种简单的方法是实施以下其中一项：

将上一个值和新值传递给递归调用，并在第一步检查它们是否相同——这可能是递归情况

传递一个变量以指示函数已被调用的次数，并任意限制其可被调用的次数

Answer 3

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

Answer 4

你需要找到一个解决办法，因为正如你所要求的，没有通用的解决方案。有关更多信息，请参见Halting problem

Answer 5

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

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

Answer 6

您只能使用程序分析来检测最微不足道的问题。你能做的最好的事情就是在你的特定环境中增加守卫，并传递一个深度级别的上下文。几乎不可能检测出一般情况并区分递归算法的合法使用