Como detectar um loop infinito em uma chamada recursiva?

Question

Eu tenho uma função que é recursiva que chama-se, e eu quero detectar e terminar se entra em um loop infinito, ou seja - sendo chamado para o mesmo problema novamente. Qual é a maneira mais fácil de fazer isso?

EDIT: Esta é a função, e ele será chamado recursivamente com diferentes valores de x e y. i deseja terminar se em uma chamada recursiva, o valor do par (x, y) é repetido.

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

Answer 1

Se a função é puramente funcional, ou seja, ele não tem efeitos estaduais ou colaterais, então você pode manter um Set dos argumentos (edit: vendo a sua edição, você iria manter um conjunto de pares de (x, y)) que tem sido chamado com, e cada vez apenas verificar se o argumento atual é no conjunto. Dessa forma, você pode detectar um ciclo, se você tiver que muito rapidamente. Mas se o espaço argumento é grande e leva muito tempo para chegar a uma repetição, você pode funcionar fora de sua memória antes de detectar um ciclo. Em geral, é claro, você não pode fazê-lo porque este é o problema da parada.

Answer 2

Uma maneira é passar uma variável depth de uma chamada para a próxima, incrementá-lo cada vez que sua função chama a si mesmo. Verifique se depth não crescer mais do que um limite particular. Exemplo:

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

Você terá que encontrar uma forma de contornar, porque, como você pediu-lo, não há nenhuma solução geral. Veja a Travar problema para mais informações.

Answer 4

Uma maneira fácil seria implementar uma das seguintes opções:

Passe o valor anterior e o novo valor para a chamada recursiva e fazer o seu primeiro passo uma verificação para ver se eles são o mesmo -. Esta é, possivelmente, o seu caso recursiva

Passar uma variável para indicar o número de vezes que a função foi chamado, e arbitrariamente limitar o número de vezes que pode ser chamado.

Answer 5

Você só pode detectar os mais triviais usando análise de programa. O melhor que você pode fazer é adicionar guardas em sua circunstância particular e passar um contexto nível de profundidade. É quase impossível detectar o caso geral e uso legítimo diferenciada de algoritmos recursivos.

Answer 6

Você pode usar a sobrecarga para uma assinatura consistente (este é o método melhor), ou você pode usar uma variável estática:

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

A resposta de John Kugelman com sobrecarga é melhor beacuse de thread-safe, enquanto variáveis ??estáticas não são.

Billy3

Answer 7

Parece que você pode estar trabalhando em uma matriz 2D. Se você tem um bit extra para poupar nos valores da matriz, você pode usá-lo como uma bandeira. Verificá-lo, e terminar a recursão se o sinalizador foi definido. Em seguida, configurá-lo antes de continuar.

Se você não tem um pouco de sobra nos valores, você sempre pode torná-lo uma matriz de objetos em seu lugar.

Answer 8

Se você quiser manter a sua assinatura do método, você poderia manter um par de conjuntos para gravar valores antigos de x e 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 9

IMHO Somente laços podem entrar em um loop infinito.

Se o seu método tem muitos nível de recursividade a JVM irá lançar um StackOverflowError. Você pode interceptar este erro com um bloco try / catch e fazer o que você pretende fazer quando esta condição ocorre.

Answer 10

A termina função recursiva no caso de uma condição for satisfeita.

Exemplos:

• O resultado de uma função é 0 ou é 1
• O número máximo de chamadas é atingido
• O resultado é inferior / superior ao valor de entrada

No seu caso, a condição é ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])

0, 1, ...N são os índices dos pares

Assim, você precisa de um recipiente (vetor, lista, mapa) para armazenar todos os pares anteriores e compará-los com o par atual.

Answer 11

As primeiras findbugs uso MVn:. Gui para abrir um gui que apontam para a linha onde o erro está presente

Eu também enfrentou o mesmo problema e eu resolvi-lo adicionando uma variável booleana na verificação loop.

Código antes ->

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

Para resolver este problema, eu só acrescentou uma variável booleana e defini-lo como falso no bloco catch. Verifique-a para baixo

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

Isto é como eu resolver este problema. Espero que isso vai ajudar. :)