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

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

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