Come funziona il backtracking ricorsivo?

Potresti tornare indietro come se stessimo attraversando un dungeon e devi esplorare tutti i percorsi nel dungeon (il dungeon è aciclico - non tornerai mai nello stesso posto indipendentemente dal percorso scelto). Quando arrivi in un luogo che si biforca su più percorsi, ne scegli solo uno e lo segui. Solo dopo che sei arrivato alla fine, torni all'ultima biforcazione e scegli il percorso successivo. Quando hai esplorato tutti i percorsi, torni al bivio precedente e ripeti fino a quando non ritorni all'inizio del dungeon.

Nel codice, il ciclo for è come il fork di un dungeon (in questo caso con 6 diversi percorsi in cui puoi continuare), la chiamata ricorsiva a diceRolls rappresenta la scelta di uno dei possibili percorsi, la fine di un dungeon è quando si interrompe la ricorsione (non si ferma l'esecuzione, si torna indietro di un passo). Ogni volta che salti fuori dalla funzione diceRolls, continui con il ciclo for e chiama di nuovo i dadi.

Finisci con l'interruzione del ciclo for da una chiamata ricorsiva nella prima iterazione all'inizio, stampando 111, quindi andando indietro di un passo e continuando il ciclo otterrai 112, quindi 113, ... 116, e tu vai indietro di un passo e ottieni 121, 122, 123, ... finché non ottieni 661, 662, 666. A quel punto tutti i tuoi loop e le tue chiamate ricorsive sono finiti e il calcolo termina.

Prova a eseguire quanto segue:

public static void diceRolls(int dice) { 
    List<Integer> chosen = new ArrayList<Integer>(); 
    diceRolls(dice, chosen); 
} 

// private recursive helper to implement diceRolls logic 
private static void diceRolls(int dice,List<Integer> chosen) {
System.out.println("Entering diceRolls with dice="+dice); 
     if (dice == 0) { 
          System.out.println(chosen); // base case 
       } else { 
          for (int i = 1; i <= 6; i++) {
               System.out.println("Starting for loop. i="+i+", dice="+dice); 
               chosen.add(i); // choose 
               diceRolls(dice - 1, chosen); // explore 
               chosen.remove(chosen.size() - 1); // un-choose 
               System.out.println("Ending for loop. i="+i+", dice="+dice);
           }
           System.out.println("Exiting diceRolls with dice="+dice); 
       }
}

Per ogni iterazione del ciclo for, verrà effettuata una nuova chiamata a dadiRoll (dadi int, Lista scelta) con dadi inferiori di un tempo a quelli precedenti. Se i dadi non sono uguali a 0, la nuova chiamata comporterà altre sei chiamate.

L'idea di backtracking è che si desidera eseguire una prima ricerca approfondita su tutte le possibili soluzioni a un problema. Diciamo che stai provando a tirare un dado N volte e stai cercando di ottenere numeri crescenti per ogni tiro. Sia [1,2,3] un tiro di 1 quindi 2 poi 3. Il tuo stato iniziale del problema sarà [], senza ancora nessun lancio. Puoi tirare un dado standard in sei modi diversi, e così dopo il tuo primo lancio avrai [1], [2], [3], [4], [5], [6]. Per ognuno di questi stati, puoi tirare un dado e aggiungere sei modi per un totale di 36 possibili stati: [1,1], [1,2], [1,3], [1,4], [1] , 5], [1,6], [2,1], [2,2] ... [6,5], [6,6]. Tuttavia, possiamo "sfoltire" stati che sono già non validi come [2,1] e [6,5] poiché non aumentano i tiri. In questo modo, è possibile eseguire una modifica aggiuntiva a ciascuna soluzione parziale del problema fino a quando non si ottengono tutte le soluzioni possibili a un problema, potando a ogni passaggio per ridurre la dimensione del problema.

La risposta di OndreJM è giusta. Per aggiungere un po 'di magia grafica, considera un semplice programma fattoriale ricorsivo e segui il diagramma di flusso.

Seguilo riga per riga, e quando premi una chiamata a una funzione, copia e incolla l'intero codice funzione al suo posto.

Pertanto, select.remove () sarà chiamato dopo che le precedenti chiamate di funzione sono terminate e quindi l'altro scelto .removes sarà chiamato prima di esso.

Google come utilizzare un debugger per inserire pause nel tuo lavoro e poi trovare le variabili in punti diversi del codice, ti aiuterà molto più a capire che a cercare di convincere qualcuno a spiegarlo.