Recursion and Backtracking in Java

Introduction

Some problems are hard to solve with a loop, yet become short and clear once you look at them the right way. This tutorial is about that way of looking - thinking recursively - and about the technique built on it for searching through choices, called backtracking. We start with a short recap of recursion, and then learn to think recursively by solving the Tower of Hanoi puzzle. We draw the tree of recursive calls, count the moves, and see why some recursion is expensive by nature while other recursion is only wasteful. The second half moves on to backtracking: the idea, the three steps which every backtracking method has, a maze solved in Java, and pruning, which cuts the search short. Every output shown comes from running the program next to it.

A Quick Recap of Recursion

A recursive method is a method which calls itself. It has two parts - a base case, which is simple enough to answer directly, and a recursive case, which calls the method on a smaller version of the same problem. Each call gets its own frame on the call stack, and if the base case is never reached the stack overflows. All of this, with factorials, recursive binary search and the cost of naive Fibonacci, is explained step by step in the Recursion in Java with ExamplesClick to read: Recursion in Java with Examples tutorial. Here we build on it.

Thinking Recursively

Knowing what recursion is does not yet tell you how to come up with a recursive solution. The trick that students find hardest, and that makes everything easy once it clicks, is this -
Assume the method already works for smaller inputs, and use it.
You do not trace the calls in your head. You ask only two questions: "what is the smallest case, which I can answer directly?" and "if somebody solved the problem for a smaller input for me, how would I use that to solve the full problem?". If both answers are right, the method is right. Teachers sometimes call this the recursive leap of faith. The best puzzle on which to practise it is the Tower of Hanoi.

The Tower of Hanoi

There are three pegs - A, B and C. On peg A there is a stack of disks of different sizes, the largest at the bottom and the smallest at the top. The task is to move the whole stack to peg C, following two rules -
  1. Only one disk can be moved at a time - the top disk of a peg.
  2. A larger disk may never be placed on a smaller disk.
Try it in your head first. With one disk it is one move, A to C. With two disks: move the small disk to B, the large disk to C, and the small disk from B to C - three moves. With three disks it already takes some thought, and with five most people give up. A loop does not help, because it is not clear what each turn of the loop should do.

Now ask the two questions. The smallest case is zero disks - there is nothing to move. For the full problem of moving n disks from A to C, imagine that somebody can already move n - 1 disks for us, following the rules. Then the solution has three steps -
  1. Move the top n - 1 disks from A to the spare peg B. (Somebody does this for us.)
  2. Move the largest disk, which is now alone on A, to C. This is one move.
  3. Move the n - 1 disks from B onto the largest disk on C. (Somebody does this again.)
The "somebody" is the same method, called with n - 1. It is allowed to use any peg as its spare, because every disk it moves is smaller than the largest disk, which is either still at the bottom of A or already at the bottom of C - so no rule can be broken. The recursive solution of the Tower of Hanoi for n disks - first the top n minus 1 disks are moved from peg A to the spare peg B, then the largest disk is moved from A to C in one move, and finally the n minus 1 disks are moved from B onto the largest disk on C; both moves of n minus 1 disks are the same problem with one disk less
Tower of Hanoi solved recursively
package com.javabrahman.algorithms.recursion;
public class TowerOfHanoi {
  static long moves;
  static void solve(int disks, char from, char to, char spare, boolean print) {
    if (disks == 0) return;
    solve(disks - 1, from, spare, to, print);
    moves++;
    if (print) System.out.println("Move disk " + disks + " from " + from + " to " + to);
    solve(disks - 1, spare, to, from, print);
  }
  public static void main(String[] args) {
    solve(3, 'A', 'C', 'B', true);
    System.out.println("Moves for 3 disks: " + moves);
    System.out.println();
    for (int n : new int[] { 1, 2, 3, 4, 5, 10, 20, 25 }) {
      moves = 0;
      solve(n, 'A', 'C', 'B', false);
      System.out.printf("%2d disks: %,12d moves  (2^%d - 1 = %,d)%n", n, moves, n, (1L << n) - 1);
    }
  }
}
 OUTPUT of the above code
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Moves for 3 disks: 7

 1 disks:            1 moves  (2^1 - 1 = 1)
 2 disks:            3 moves  (2^2 - 1 = 3)
 3 disks:            7 moves  (2^3 - 1 = 7)
 4 disks:           15 moves  (2^4 - 1 = 15)
 5 disks:           31 moves  (2^5 - 1 = 31)
10 disks:        1,023 moves  (2^10 - 1 = 1,023)
20 disks:    1,048,575 moves  (2^20 - 1 = 1,048,575)
25 disks:   33,554,431 moves  (2^25 - 1 = 33,554,431)
Look at how short solve() is. The base case is the if (disks == 0) return;. The three steps of the idea are the three lines after it - move n - 1 disks to the spare, move the largest disk, move n - 1 disks from the spare to the target. Notice how the roles of the pegs are passed on: in the first call the spare peg becomes the target, and in the second call the source peg becomes the spare. We never had to work out the individual moves; the method found all seven of them for three disks, in the correct order, and you can check each one against the rules.

The Recursion Tree

To understand how much work a recursive method does, draw its recursion tree: every call is a node, and the calls it makes are its children. A method like factorial, which makes one call, gives a tree which is just a chain - n calls for an input of n. The Hanoi method makes two calls, each with one disk less, so the tree doubles at every level. The recursion tree of solve for 3 disks - solve(3) calls solve(2) twice, each solve(2) calls solve(1) twice, and each solve(1) calls solve(0) twice; every call with at least one disk makes exactly one move between its two calls, so the tree makes 1 plus 2 plus 4 equals 7 moves, which is 2 to the power 3 minus 1 Every call with at least one disk makes exactly one move. Count the calls level by level: 1 call with n disks, 2 calls with n - 1 disks, 4 calls with n - 2 disks, and so on down to 2n-1 calls with one disk. Together that is 1 + 2 + 4 + ... + 2n-1 = 2n - 1 moves, and this is exactly what the second part of the output shows: 7 moves for 3 disks, 1,023 for 10 disks, and over 33 million for 25 disks. In the language of Big-O notationClick to read tutorial: Big-O Notation Explained with Java Examples the Tower of Hanoi is O(2n). The legend has the puzzle being solved with 64 disks; at one move per second, 264 - 1 moves would take about 585 billion years.

Here is a question worth pausing on. The naive recursive Fibonacci method is also O(2n), and the Recursive Fibonacci with memoizationClick to read: Recursive Fibonacci with memoization tutorial shows how storing the results which have already been calculated makes it dramatically faster. Each Fibonacci number is then calculated only once, so the work drops to O(n). Can the same trick make the Tower of Hanoi faster? No - and the reason is the important part. Fibonacci's tree calculates the same values again and again, so most of its calls are wasted work. Hanoi's tree has no repeated work at all: every one of its 2n - 1 moves is a different, necessary move, and it can be proved that no solution needs fewer. So when a recursion tree is large, ask whether its nodes repeat. If they do, the recursion is only wasteful and can be fixed. If they do not, the problem itself is that big.

Backtracking

Now for the second idea of this tutorial. Many problems ask you to find something among a huge number of possibilities: a path through a maze, a placement of pieces on a board, a combination of items which satisfies some rules. You cannot write a formula for the answer, but you can try possibilities one by one. Backtracking is the systematic way of doing this with recursion. Think of walking through a maze with a piece of chalk. At every junction you pick a passage and mark it. If you reach a dead end, you walk back - you backtrack - to the last junction, and try the next passage which you have not tried yet. If all passages from a junction lead to dead ends, you walk back to the junction before it. Because you never try the same passage twice, you either reach the exit or prove that there is none. Every backtracking method follows the same three steps -
  1. Choose - make one of the possible choices, and record it.
  2. Explore - call the method recursively, to continue from the new position.
  3. Unchoose - if that did not lead to a solution, undo the choice, and try the next one.
The shape of every backtracking method
boolean solve(state) {
  if (state is a solution) return true;        // base case: found
  if (state breaks a rule) return false;       // base case: dead end
  for (each possible choice) {
    make the choice;                           // choose
    if (solve(new state)) return true;         // explore
    undo the choice;                           // unchoose
  }
  return false;                                // no choice worked: backtrack
}
The calls form a tree here as well, called the state space tree. Its root is the starting position, each branch is a choice, the dead ends are leaves which fail, and a solution is a leaf which succeeds. Backtracking walks this tree depth first - it follows one branch as far as it goes before trying the next one. A state space tree explored by backtracking - from the start, choice 1 leads to a dead end, so the search backtracks and tries choice 2; under choice 2, the first option is a dead end too, the search backtracks again, and the second option reaches the solution; branches after the solution are never explored

Solving a Maze with Backtracking

Lets turn the chalk idea into Java. The maze below is a grid of characters: S is the start, E the exit, # a wall and . an open cell. From a cell we may move down, right, up or left. The method marks the cells of the current path with * (the chalk), and when a cell turns out to be a dead end, it changes the mark to x, so that it is never tried again, and prints a line.
Solving a maze with backtracking
package com.javabrahman.algorithms.recursion;
public class MazeSolver {
  static char[][] maze = {
      "S.#....".toCharArray(),
      ".##.##.".toCharArray(),
      "...#...".toCharArray(),
      ".#...#.".toCharArray(),
      ".#.#..E".toCharArray() };
  static boolean solve(int row, int col) {
    if (row < 0 || col < 0 || row >= maze.length || col >= maze[0].length) return false;
    char cell = maze[row][col];
    if (cell == 'E') return true;
    if (cell == '#' || cell == '*' || cell == 'x') return false;
    maze[row][col] = '*';
    if (solve(row + 1, col) || solve(row, col + 1) || solve(row - 1, col) || solve(row, col - 1)) {
      return true;
    }
    maze[row][col] = 'x';
    System.out.println("dead end at row " + row + ", column " + col + " - backtracking");
    return false;
  }
  public static void main(String[] args) {
    boolean found = solve(0, 0);
    System.out.println(found ? "Path found:" : "No path");
    for (char[] line : maze) System.out.println("  " + new String(line));
  }
}
 OUTPUT of the above code
dead end at row 4, column 0 - backtracking
dead end at row 3, column 0 - backtracking
dead end at row 4, column 2 - backtracking
Path found:
  *.#....
  *##.##.
  ***#...
  x#***#.
  x#x#**E
Match the code with the three steps. The first four lines of solve() are the base cases: outside the grid, a wall, or a cell which is already on the path or known to be a dead end means failure, and the exit means success. Choose is maze[row][col] = '*'. Explore is the line with the four recursive calls - the || operator tries them one after the other and stops at the first which succeeds. Unchoose is maze[row][col] = 'x', reached only when all four directions failed. Now read the output like the trail of the search. From the start, the method first went down, as far as the bottom row. At row 4, column 0 every direction was blocked, so it printed the first dead end and backtracked to row 3, column 0 - which had no other way either, so it backtracked again. Back at row 2 it tried going right, and later found one more dead end at row 4, column 2, before reaching the exit. The final grid shows the path in * (the S is overwritten by the first *) and the three dead ends in x. The cells in the top right part of the maze were never visited, because the exit was found before the search got there.

Pruning: Cutting the Search Short

The maze solver stops at the first path it finds, which is not necessarily the shortest. To find the shortest path, backtracking has to look at every path from start to exit and keep the best. That can be a lot of work, and this is where pruning comes in: if a partial path can no longer lead to a better answer, stop exploring it immediately, instead of finding out at the end. Here the rule is simple - if the path so far is already as long as the best complete path found, no continuation of it can be shorter, so give up on it. The program below searches a maze for the shortest path twice, once without and once with this rule, and counts the calls of explore(). After visiting a cell it removes the mark again (visited[row][col] = false) - this is the unchoose step, which here is needed so that the cell can be part of other paths which are tried later.
Finding the shortest path, with and without pruning
package com.javabrahman.algorithms.recursion;
public class MazeShortest {
  static String[] plan = {
      "S....#",
      ".##...",
      "......",
      ".#.##.",
      ".....E" };
  static char[][] maze;
  static boolean[][] visited;
  static long calls;
  static int best;
  static boolean prune;
  static void explore(int row, int col, int length) {
    calls++;
    if (row < 0 || col < 0 || row >= maze.length || col >= maze[0].length) return;
    if (maze[row][col] == '#' || visited[row][col]) return;
    if (prune && length >= best) return;
    if (maze[row][col] == 'E') {
      best = Math.min(best, length);
      return;
    }
    visited[row][col] = true;
    explore(row + 1, col, length + 1);
    explore(row, col + 1, length + 1);
    explore(row - 1, col, length + 1);
    explore(row, col - 1, length + 1);
    visited[row][col] = false;
  }
  static void run(boolean withPruning) {
    maze = new char[plan.length][];
    for (int r = 0; r < plan.length; r++) maze[r] = plan[r].toCharArray();
    visited = new boolean[maze.length][maze[0].length];
    calls = 0;
    best = Integer.MAX_VALUE;
    prune = withPruning;
    explore(0, 0, 0);
    System.out.println((withPruning ? "with pruning   " : "without pruning") + ": shortest path " + best + " steps, " + calls + " calls");
  }
  public static void main(String[] args) {
    run(false);
    run(true);
  }
}
 OUTPUT of the above code
without pruning: shortest path 9 steps, 1237 calls
with pruning   : shortest path 9 steps, 329 calls
Both searches find the same answer, a shortest path of 9 steps, but the pruned search needs 329 calls instead of 1,237 - almost three quarters of the work is skipped, and the answer is still guaranteed to be the shortest, because only paths which could not have won were dropped. On a larger maze the difference grows very quickly, as the number of possible paths grows exponentially with the size of the maze. Good pruning is the difference between a backtracking program which answers in a second and one which never finishes. A note for later: for the shortest path in a maze specifically, there is a faster method which does not backtrack at all - breadth-first search, which will be covered in its own tutorial in this series. Backtracking shines when the problem has rules which a solution must satisfy - placing queens, filling a Sudoku, choosing items - and those classic problems will have a tutorial of their own in this series as well.

When to Use Recursion and Backtracking

  • Use recursion when the problem contains smaller copies of itself - nested structures such as trees and folders, divide-and-conquer algorithms such as Merge SortClick to read: Merge Sort and Quick SortClick to read tutorial: Quick Sort in Java, and puzzles like the Tower of Hanoi.
  • Use backtracking when you must search through combinations of choices, a solution has to satisfy rules, and a partial choice can be recognised as hopeless early.
  • Watch the recursion tree. If the same calls repeat, remember their results, or use a loop. If they do not repeat but the tree is huge, look for pruning rules, or for a different algorithm altogether.
  • Watch the depth. Every level of recursion is a frame on the call stack. A recursion which is thousands of levels deep can end in a StackOverflowError, so for very deep problems a loop with an explicit stack is safer.

Summary

In this tutorial on recursion and backtracking in java we recapped what a recursive method is, and then learnt to think recursively by assuming that the method already works for smaller inputs. With that idea we solved the Tower of Hanoi in a few lines, drew its recursion tree, and counted 2n - 1 moves, which we checked with a program. We saw that a large recursion tree is wasteful when its calls repeat, as in naive Fibonacci, but unavoidable when they do not, as in Hanoi. We then learnt backtracking - choose, explore, unchoose - and the state space tree it walks, solved a maze with it, and finally used pruning to find the shortest path in a maze with 329 calls instead of 1,237.