How does recursive backtracking work ?

Question

I am trying to figure out recursive backtracking, i have good understanding of recursion and till some extent the concept of backtracking too but i am having difficulty understand the chronological order of how things are working when for loop is being used in following code.

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) { 
     if (dice == 0) { 
          System.out.println(chosen); // base case 
       } else { 
          for (int i = 1; i <= 6; i++) { 
               chosen.add(i); // choose 
               diceRolls(dice - 1, chosen); // explore 
               chosen.remove(chosen.size() - 1); // un-choose 
      } 
  } 
}

Now i am having problem understand that for example we pass 3 in diceRolls function, it calls the helper method, inside the for loop we add all the value of i (ie 1) after that it calls the method again so does the for loop complete itself before recursing or the method diceRolls(2,chosen) is passed now ? Because if 2 is passed then also the loop would only run once before recursing itself.

Answer 1

You may imageine backtrack as if you were walking through a dungeon and you must explore all the paths in the dungeon (the dungeon is acyclic - you will never come back to the same place regardless the path you choose). When you come to a place which forks to multiple paths, you choose only one and follow it. Only after you come to an end, you go back to the last fork and choose the next path. When you explored all paths, you go back to previous fork and repeat until you come back to the beginning of the dungeon.

In the code, the for cycle is like the fork in dungeon (in this case with 6 different path where you can continue), the recursive call to diceRolls represents choosing one of the possible paths, the end of a dungeon is when you stop the recursion (you don't stop the execution, you just come one step back). Every time you jump out of the diceRolls function, you continue with the for loop and call diceRolls again.

You end up with interrupting the for loop by a recursive call in the first iteration in the beginning, printing 111, then going one step back and continuing the loop you will get 112, then 113, ...116, and the you go even one step back and get 121, 122, 123,... until you get 661, 662, 666. At that point all your loops and recursive calls finished and the computation ends.

Answer 2

Try running the following:

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

For each iteration of the for loop, a new call will be made to diceRolls(int dice,List chosen) with dice being one less than it was before. If dice is not equal to 0, then that new call will result in six more calls being made.

The idea of backtracking is that you want to perform a depth first search across all possible solutions to a problem. Let's say you're trying to roll a dice N times and you're trying to get increasing numbers for each roll. Let [1,2,3] denote a roll of 1 then 2 then 3. Your initial state of the problem will be [], with no rolls performed yet. You can roll a standard dice six different ways, and so after your first roll you will have [1], [2], [3], [4], [5], [6]. For each one of these states, you can roll a dice an addition six ways for a total of 36 possible states: [1,1], [1,2], [1,3], [1,4], [1,5], [1,6], [2,1], [2,2]...[6,5], [6,6]. However, we can 'prune' states that are already invalid such as [2,1] and [6,5] as they are not increasing rolls. In this way, we can perform one addition change to each partial solution to the problem until we get all possible solutions to a problem, pruning at each step to reduce the problem size.

Answer 3

OndreJM's answer is on point. Just to add a little diagramatic magic, consider a simple recursive factorial program and follow the flowchart.

Answer 4

Just follow it line by line, and when you hit a function call imagine copying and pasting the entirety of that function code in its place.

Therefore chosen.remove() will be called after the previous function calls have ended and therefore the other chosen.removes shall be called prior to it.

Google how to use a debugger put breaks in your work and then find what the variables are at different points of your code it will help your understanding a lot more than trying to get someone to explain it.