¿Cómo detectar un bucle infinito en una llamada recursiva?

Question

Tengo una función que se llama a sí misma de forma recursiva, y quiero detectar y terminar si entra en un bucle infinito, es decir, recibir nuevamente el mismo problema. Cual es la forma mas fácil de hacer eso?

EDITAR: Esta es la función, y se llamará recursivamente con diferentes valores de x e y. Quiero terminar si en una llamada recursiva, el valor del par (x, y) se repite.

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

Answer 1

Si la función es puramente funcional, es decir, no tiene estado ni efectos secundarios, entonces podría mantener un Set de los argumentos (edit: al ver su edición, mantendría un conjunto de pares de (x, y)) con el que se ha llamado, y cada vez simplemente verifique si el argumento actual está en el conjunto. De esa manera, puede detectar un ciclo si se encuentra con él bastante rápido. Pero si el espacio de discusión es grande y lleva mucho tiempo volver a repetir, puede quedarse sin memoria antes de detectar un ciclo. En general, por supuesto, no puede hacerlo porque este es el problema de detención.

Answer 2

Una forma es pasar una variable profundidad de una llamada a la siguiente, incrementándola cada vez que su función se llame a sí misma. Verifique que depth no crezca más que algún umbral en particular. Ejemplo:

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

Deberá encontrar una solución alternativa, porque, como lo ha pedido, no hay una solución general. Consulte el Problema de detención para obtener más información.

Answer 4

Una manera fácil sería implementar uno de los siguientes:

Pase el valor anterior y el nuevo valor a la llamada recursiva y compruebe su primer paso para ver si son iguales; este es posiblemente su caso recursivo.

Pase una variable para indicar el número de veces que se ha llamado a la función y limite arbitrariamente el número de veces que se puede llamar.

Answer 5

Solo puede detectar los más triviales mediante el análisis de programas. Lo mejor que puede hacer es agregar guardias en su circunstancia particular y pasar un contexto de nivel de profundidad. Es casi imposible detectar el caso general y diferenciar el uso legítimo de algoritmos recursivos.

Answer 6

Puede usar la sobrecarga para una firma coherente (este es el mejor método), o puede usar una variable 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;
}

La respuesta de John Kugelman con sobrecarga es mejor porque es segura para subprocesos, mientras que las variables estáticas no lo son.

Billy3

Answer 7

Parece que podría estar trabajando en una matriz 2D. Si tiene un bit adicional de sobra en los valores de la matriz, puede usarlo como indicador. Verifíquelo y finalice la recursividad si se ha establecido el indicador. Luego configúrelo antes de continuar.

Si no tiene un poco de sobra en los valores, siempre puede convertirlo en una matriz de objetos.

Answer 8

Si desea mantener la firma de su método, puede conservar un par de conjuntos para registrar valores antiguos 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

En mi humilde opinión, los bucles solo pueden entrar en un bucle infinito.

Si su método tiene demasiados niveles de recursión, la JVM arrojará un StackOverflowError. Puede atrapar este error con un bloque try / catch y hacer lo que planee hacer cuando ocurra esta condición.

Answer 10

Una función recursiva termina en caso de que se cumpla una condición.

Ejemplos:

• El resultado de una función es 0 o es 1
• Se alcanza el número máximo de llamadas
• El resultado es menor / mayor que el valor de entrada

En su caso, la condición es ([x0, y0] == [xN, yN]) OR ([x1, y1] == [xN, yN]) OR ([xN-1, yN- 1] == [xN, yN])

0, 1, ... N son los índices de los pares

Por lo tanto, necesita un contenedor (vector, lista, mapa) para almacenar todos los pares anteriores y compararlos con el par actual.

Answer 11

Primero use mvn findbugs: gui para abrir una gui que apunte a la línea donde está presente este error.

También enfrenté el mismo problema y lo resolví agregando una variable booleana en la verificación del bucle.

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, simplemente agregué una variable booleana y la configuré como falsa en el bloque catch. Compruébalo abajo

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

Así es como resolví este problema. Espero que esto ayude. :)