Come rilevare un ciclo infinito in una chiamata ricorsiva?

Question

Ho una funzione che si chiama ricorsivamente da sola, e voglio rilevare e terminare se va in un ciclo infinito, cioè - essere chiamato di nuovo per lo stesso problema. Qual è il modo più semplice per farlo?

EDIT: questa è la funzione e verrà chiamata in modo ricorsivo con valori diversi di xey. voglio terminare se in una chiamata ricorsiva si ripete il valore della coppia (x, y).

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

Answer 1

Se la funzione è puramente funzionale, cioè non ha stato o effetti collaterali, allora potresti mantenere un Set degli argomenti (modifica: vedendo la tua modifica, manterresti un insieme di coppie di (x, y)) con cui è stato chiamato e ogni volta controlla solo se l'argomento corrente è nell'insieme. In questo modo, puoi rilevare un ciclo se lo incontri abbastanza rapidamente. Ma se lo spazio degli argomenti è grande e ci vuole molto tempo per arrivare a una ripetizione, potresti esaurire la memoria prima di rilevare un ciclo. In generale, ovviamente, non puoi farlo perché questo è il problema di arresto.

Answer 2

Un modo è passare una variabile depth da una chiamata alla successiva, incrementandola ogni volta che la tua funzione si chiama da sola. Verifica che depth non cresca oltre una determinata soglia. Esempio:

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

Dovrai trovare una soluzione, perché, come hai chiesto, non esiste una soluzione generale. Vedi il Problema di arresto per maggiori informazioni.

Answer 4

Un modo semplice sarebbe implementare uno dei seguenti:

Passa il valore precedente e il nuovo valore alla chiamata ricorsiva e fai il tuo primo passo un controllo per vedere se sono uguali - questo è probabilmente il tuo caso ricorsivo.

Passa una variabile per indicare il numero di volte in cui la funzione è stata chiamata e limita arbitrariamente il numero di volte che può essere chiamata.

Answer 5

Puoi rilevare solo quelli più banali usando l'analisi del programma. Il meglio che puoi fare è aggiungere protezioni nella tua particolare circostanza e superare un contesto di livello di profondità. È quasi impossibile rilevare il caso generale e differenziare l'uso legittimo di algoritmi ricorsivi.

Answer 6

Puoi utilizzare l'overloading per una firma coerente (questo è il metodo migliore) oppure puoi utilizzare una variabile statica:

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 risposta di John Kugelman con sovraccarico è migliore perché è sicura per i thread, mentre le variabili statiche no.

Billy3

Answer 7

Sembra che tu stia lavorando su un array 2D. Se hai un po 'di più da risparmiare nei valori dell'array, puoi usarlo come flag. Controllalo e termina la ricorsione se la bandiera è stata impostata. Quindi impostalo prima di continuare.

Se non hai un po 'di risparmi nei valori, puoi sempre renderlo un array di oggetti.

Answer 8

Se si desidera mantenere la firma del metodo, è possibile conservare un paio di set per registrare i vecchi valori di xe 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 Solo i loop possono andare in un loop infinito.

Se il tuo metodo ha troppi livelli di ricorsione, la JVM genererà StackOverflowError. Puoi intercettare questo errore con un blocco try / catch e fare tutto ciò che prevedi di fare quando si verifica questa condizione.

Answer 10

Una funzione ricorsiva termina nel caso in cui una condizione sia soddisfatta.

Esempi:

• Il risultato di una funzione è 0 o 1
• È stato raggiunto il numero massimo di chiamate
• Il risultato è inferiore / maggiore del valore di input

Nel tuo caso la condizione è ([x0, y0] == [xN, yN]) OR ([x1, y1] == [xN, yN]) OR ([xN-1, yN- 1] == [xN, yN])

0, 1, ... N sono gli indici delle coppie

Pertanto è necessario un contenitore (vettore, elenco, mappa) per memorizzare tutte le coppie precedenti e confrontarle con la coppia corrente.

Answer 11

Primo utilizzo mvn findbugs: gui per aprire una gui che punta alla linea in cui è presente questo errore.

Ho anche riscontrato lo stesso problema e l'ho risolto aggiungendo una variabile booleana nella verifica del ciclo.

Codice precedente - >

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

Per risolvere questo problema, ho appena aggiunto una variabile booleana e l'ho impostata su false nel blocco catch. Dai un'occhiata

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

Ecco come ho risolto questo problema. Spero che questo possa aiutare. :)