Where in this sample code is the backtracking happening?

Question

package maze;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class Maze {


    public static void main(String[] args) {
        int board[][] = new int[31][121];
        Random rand = new Random();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j]=1;
            }
        }
        int r = rand.nextInt(board.length);
        while(r%2==0){
            r=rand.nextInt(board.length);
        }

        int c = rand.nextInt(board[0].length);
        while(c%2==0){
            c=rand.nextInt(21);
        }
        System.out.format("r is %d and c is %d\n",r,c);
        board[r][c]=0;
        recursion(r,c,board);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j]==1) {
                    System.out.print("#");
                } else if (board[i][j]==0) {
                    System.out.print(" ");
                }

            }
            System.out.println("");
        }

    }
    public static void recursion(int r, int c,int[][] board){
        ArrayList<Integer> randDirections = generateDirections();
        int[] randDir=new int[randDirections.size()];

        for (int i = 0; i < randDir.length; i++) {
            randDir[i]=randDirections.get(i);
            System.out.println(randDir[i]);
        }

        for (int i = 0; i < randDir.length; i++) {

            switch(randDir[i]){
                case 1:
                    //checks up position
                    if (r-2>=0) {
                        if (board[r-2][c]!=0) {
                            board[r-2][c] = 0;
                            board[r-1][c] = 0;
                            recursion(r - 2, c,board);
                        }
                    }
                    break;
                case 2:
                    //checks right position
                    if (c + 2 <= board[0].length - 1){
                        if (board[r][c + 2] != 0) {
                            board[r][c + 2] = 0;
                            board[r][c + 1] = 0;
                            recursion(r, c + 2,board);
                        }
                    }
                    break;
                case 3:
                    //checks down position
                    if (r + 2 <= board.length - 1){
                        if (board[r + 2][c] != 0) {
                            board[r+2][c] = 0;
                            board[r+1][c] = 0;
                            recursion(r + 2, c,board);
                        }
                    }
                    break;
                case 4:
                    //checks left position
                    if (c - 2 >= 0){
                        if (board[r][c - 2] != 0) {
                            board[r][c - 2] = 0;
                            board[r][c - 1] = 0;
                            recursion(r, c - 2,board);
                        }
                    }
                    break;
            }  
        }
    }
    public static ArrayList<Integer> generateDirections(){
        ArrayList<Integer> randoms = new ArrayList();
        for (int i = 0; i < 4; i++) {
            randoms.add(i+1);
        }
        Collections.shuffle(randoms);
        return randoms;
    }
}

I can see that my program is backtracking when it cannot make another path for my maze and that my recursion method only stops when it has backtracked all the way back to the first path square. However, I don't know exactly what is doing this. It seems to me that the method should just stop when the for loop of the four random directions is exhausted. Could someone explain to me which part of code is causing it to backtrack and how it works?

Answer 1

The answer lies in the call stack and understanding what is happening at each level of the stack. "Backtracking" is occurring when one recursive call exhausts its for-loop, after which time, the method returns, popping one level off the stack, and the continuing in the for-loop of the context of the stack level that made the call.

Mapping out just 2 levels of calls can help clarify. You'll find in the first "level" (the root call of the recursion), the for loop simply iterates as you would expect, but it will be interspersed with the processing of the recursive calls it makes (each creating a "next level" of recursion).

The for loop of the bottom layer of the calling stack goes through all of its iterations while the for loop of the layer above may be on only the first iteration.