Recursion and Backtracking

Imagine you are standing somewhere in a long queue and want to know how many people are ahead of you. You cannot see the front. So you ask the person in front: "How many people are ahead of you?" They ask the person in front of them, and so on. The first person in the queue says "zero, nobody". The next says "one", the next "two", and the answers travel back down the line until you hear yours.

Nobody had to see the whole queue. Each person only did two things: if I am first, answer 0; otherwise ask the person ahead and add one. That is recursion: solving a problem by solving a slightly smaller version of the same problem, until the problem becomes so small the answer is obvious.

Recursion is the key that unlocks trees, divide and conquer, dynamic programming, and a family of search problems called backtracking. It feels strange at first, which is normal. This article builds the intuition step by step.

• The anatomy of a recursive method: base case and recursive case.
• How the call stack works, and what StackOverflowError means.
• How to estimate running time by drawing a recursion tree.
• How to think recursively without tracing every call.
• The backtracking pattern: choose, explore, undo.
• How to generate subsets, permutations and combinations, avoid duplicates, prune, and solve N-Queens.

Every recursive method has two parts:

1. A base case: an input so small that the answer is immediate, with no further recursion.
2. A recursive case: the method calls itself on a smaller input and uses that result to build the answer.

answer(problem):    if problem is tiny:                   // base case        return the obvious answer    smaller = a slightly smaller problem  // makes progress    return combine(answer(smaller))       // recursive case

Two things must be true or the recursion never ends:

• Every possible input eventually reaches a base case.
• Each recursive call moves toward a base case (smaller number, shorter list, fewer choices).

The classic first example is the factorial: n! = n × (n - 1) × ... × 1. The base case is 0! = 1 (and 1! = 1). The recursive case is n! = n × (n - 1)!.

Beginners often try to follow every call all the way down, and get lost. Instead use this mental trick: assume the method already works correctly for smaller inputs, and only check that this call uses that result correctly. For the factorial, assume factorial(n - 1) gives the right answer. Then n * factorial(n - 1) is clearly right. Plus the base case is right. Done. This is the same logic as mathematical induction, and it is how you design recursive solutions.

When a method calls another method (including itself), the computer sets aside a block of memory for the new call, called a stack frame. It holds the parameters and local variables. Frames are stacked on top of each other. When a call returns, its frame is removed and the caller continues. This is exactly the stack data structure from Stacks and Queues.

Let us watch factorial(3). Time moves downward in this diagram.

call factorial(3)         waits for factorial(2)  call factorial(2)       waits for factorial(1)    call factorial(1)     base case: returns 1  factorial(2) resumes: 2 * 1 = 2, returns 2factorial(3) resumes: 3 * 2 = 6, returns 6

The following program shows the down phase (calls) and the up phase (returns) with printing, and some basic recursive functions:

// File: Main.javapublic class Main {    static void trace(int n) {        if (n == 0) {            System.out.println("base");            return;        }        System.out.println("down " + n);        trace(n - 1);        System.out.println("up " + n);       // runs after the deeper call returns    }    static long factorial(int n) {        if (n <= 1) {            return 1;                        // base case        }        return n * factorial(n - 1);         // recursive case    }    static int sumDigits(int n) {        if (n < 10) {            return n;                        // one digit left        }        return n % 10 + sumDigits(n / 10);   // last digit plus the digits of the rest    }    // Fast exponentiation: base^exp for exp >= 0. Halves the exponent each time.    static long power(long base, int exp) {        if (exp == 0) {            return 1;        }        long half = power(base, exp / 2);        if (exp % 2 == 0) {            return half * half;        }        return half * half * base;    }    public static void main(String[] args) {        trace(3);        System.out.println(factorial(5) + " " + factorial(20) + " " + factorial(21));        System.out.println(sumDigits(9875) + " " + sumDigits(0));        System.out.println(power(2, 10) + " " + power(3, 0) + " " + power(5, 3) + " " + power(2, 62));    }}

down 3down 2down 1baseup 1up 2up 3120 2432902008176640000 -424929004941921484829 01024 1 125 4611686018427387904

Things to learn from the output:

• The down lines come in order 3, 2, 1, then base, and then the up lines come in the opposite order. Code placed after the recursive call runs while the stack unwinds. Code before it runs while the stack grows.
• factorial(21) printed a negative number. The true value is larger than a long can hold, so it wrapped around silently, just as with int overflow in Java Essentials. For larger inputs you would need BigInteger.
• sumDigits(0) is 0, and power(2, 62) is exactly 2^62. Going to power(2, 63) would overflow a long.

Here is the dry run of power(2, 10). The exponent halves each time, so there are very few calls:

Five calls instead of ten multiplications. In general there are about log2(exp) + 1 calls, so the time is O(log exp). We use the same halving idea in binary search and in Bit Manipulation and Mathematical Patterns.

Each pending call costs memory. Java gives a thread a limited stack, typically around one megabyte by default, enough for roughly some thousands to tens of thousands of simple frames. If recursion goes too deep, or never ends, Java throws StackOverflowError.

// File: Main.javapublic class Main {    static int depth = 0;    static void recurseForever() {          // no base case!        depth++;        recurseForever();    }    static long sumTo(int n) {        if (n == 0) {            return 0;        }        return n + sumTo(n - 1);            // depth n    }    public static void main(String[] args) {        System.out.println(sumTo(5000));        try {            recurseForever();        } catch (StackOverflowError e) {            System.out.println("StackOverflowError caught; reached more than 1000 levels: " + (depth > 1000));        }    }}

12502500StackOverflowError caught; reached more than 1000 levels: true

The exact depth at which it fails varies with the machine and settings, so we only print that it went past 1,000. The practical lessons:

• A recursion that goes n levels deep uses O(n) space on the stack, even if it allocates nothing else.
• A missing or unreachable base case causes a StackOverflowError.
• Java does not optimise away the stack for "tail" calls, so a loop is safer when the depth could reach tens of thousands. If an input of n = 100,000 would recurse that deep, convert the recursion into a loop, or use an explicit stack.

Draw each call as a node, with its recursive calls as children. The total work is the work done in all the nodes.

• One call that shrinks by 1 (factorial, sumTo): a straight line of n calls. Time O(n).
• One call that halves the input (power, binary search): a line of about log n calls. Time O(log n).
• Two calls that each shrink by 1 (naive Fibonacci): the tree doubles at every level. About 2^n nodes. Time O(2^n).
• Two calls that each handle half, plus linear work to combine (merge sort): log n levels, n work on each level. Time O(n log n).

fib(4)├── fib(3)│   ├── fib(2)│   │   ├── fib(1)│   │   └── fib(0)│   └── fib(1)└── fib(2)    ├── fib(1)    └── fib(0)

You can see fib(2) appears twice. Repeated work like this is what dynamic programming removes, in Dynamic Programming Foundations. We counted the calls in the complexity article: fib(30) made 2,692,537 of them.

Anything recursive can be written with a loop (and sometimes an explicit stack), and vice versa. Choose by clarity and safety:

Some problems ask for all solutions, or the existence of one, among many possibilities: all subsets of a set, all orderings of items, all ways to place queens on a board. The brute-force idea is to build a solution one decision at a time and explore every option.

Backtracking is that idea, done carefully:

1. Choose one option for the next decision.
2. Explore by recursing to make the remaining decisions.
3. Undo the choice (the "backtrack") so the next option starts from a clean state.

And it adds pruning: if a partial solution can already be seen to be impossible, abandon it immediately and skip everything below it.

backtrack(partial solution):    if the partial solution is complete:        record it        return    for each option available now:        if the option is not allowed:      // pruning            continue        apply the option                   // choose        backtrack(updated partial solution) // explore        undo the option                    // un-choose

Picture it as a decision tree. Each node is a partial solution, each edge is a choice. Backtracking walks this tree depth first, and the "undo" step moves back up an edge.

Problem. Given distinct integers, return all subsets (the power set). For [1, 2, 3] there are 2^3 = 8: [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3].

Approach. Keep a list current for the subset we are building. Every current we reach is itself a valid subset, so record it at the start of each call. Then, for each element from position start onwards, add it, recurse with start = i + 1 (so we never reuse or reorder elements), and remove it again.

The start parameter is what prevents [1, 2] and [2, 1] from both being generated: elements are only ever added in increasing index order.

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static void subsets(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {        result.add(new ArrayList<>(current));          // copy! current keeps changing later        for (int i = start; i < nums.length; i++) {            current.add(nums[i]);                      // choose            subsets(nums, i + 1, current, result);     // explore            current.remove(current.size() - 1);        // undo: remove the LAST element by index        }    }    // Variant for input with duplicates: sort first, then skip a value equal to the previous one at the same level.    static void subsetsWithDuplicates(int[] sorted, int start, List<Integer> current, List<List<Integer>> result) {        result.add(new ArrayList<>(current));        for (int i = start; i < sorted.length; i++) {            if (i > start && sorted[i] == sorted[i - 1]) {                continue;                              // same value already tried at this position            }            current.add(sorted[i]);            subsetsWithDuplicates(sorted, i + 1, current, result);            current.remove(current.size() - 1);        }    }    public static void main(String[] args) {        List<List<Integer>> all = new ArrayList<>();        subsets(new int[] {1, 2, 3}, 0, new ArrayList<>(), all);        System.out.println(all.size() + " " + all);        List<List<Integer>> unique = new ArrayList<>();        subsetsWithDuplicates(new int[] {1, 2, 2}, 0, new ArrayList<>(), unique);        System.out.println(unique.size() + " " + unique);        List<List<Integer>> none = new ArrayList<>();        subsets(new int[] {}, 0, new ArrayList<>(), none);        System.out.println(none);    }}

8 [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]6 [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]][[]]

Three details deserve attention:

1. new ArrayList<>(current) makes a copy. If you wrote result.add(current), every entry in result would be the same list object, which keeps changing and ends up empty or wrong. Always copy before you save.
2. current.remove(current.size() - 1) removes by index. On a List<Integer>, remove(int) is an index and remove(Object) is a value, as we saw in the Java article. Here the argument is an int, so it is an index, which is what we want.
3. Duplicates. For [1, 2, 2], without the continue line, the subset [1, 2] appears twice (once using the first 2, once using the second), and [2] appears twice. After sorting, equal values sit together. The rule i > start && sorted[i] == sorted[i - 1] means: "if I am not the first option at this level, and I equal the one before me, skip me, because I would produce the same results".

Dry run of the duplicate-safe version on [1, 2, 2] (indexes 0, 1, 2):

Six subsets, no duplicates.

Complexity. There are 2^n subsets. Copying each takes up to n steps, so time is O(n × 2^n). The recursion depth is at most n, so extra space excluding the output is O(n). The output itself needs O(n × 2^n) space.

Problem. Return all orderings of distinct numbers. For [1, 2, 3] there are 3! = 6.

Here the choice at each step is "which not-yet-used element goes in the next position". A boolean[] used array records which are taken. Unlike subsets, we loop over all positions each time, skipping used ones.

Problem. Return all ways to choose k numbers from 1..n. For n = 4, k = 2: [1,2] [1,3] [1,4] [2,3] [2,4] [3,4].

This is like subsets, but we only record when the size reaches k, and we can prune: if there are not enough numbers left to fill the combination, stop looping. If we have current.size() numbers and need k - current.size() more, the next number can be at most n - (k - current.size()) + 1.

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static void permutations(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {        if (current.size() == nums.length) {            result.add(new ArrayList<>(current));            return;        }        for (int i = 0; i < nums.length; i++) {            if (used[i]) {                continue;                               // already placed            }            used[i] = true;                             // choose            current.add(nums[i]);            permutations(nums, used, current, result);  // explore            current.remove(current.size() - 1);         // undo            used[i] = false;        }    }    static void combinations(int n, int k, int start, List<Integer> current, List<List<Integer>> result) {        if (current.size() == k) {            result.add(new ArrayList<>(current));            return;        }        int stillNeeded = k - current.size();        for (int i = start; i <= n - stillNeeded + 1; i++) {   // pruning: leave room for the rest            current.add(i);            combinations(n, k, i + 1, current, result);            current.remove(current.size() - 1);        }    }    public static void main(String[] args) {        List<List<Integer>> perms = new ArrayList<>();        permutations(new int[] {1, 2, 3}, new boolean[3], new ArrayList<>(), perms);        System.out.println(perms.size() + " " + perms);        List<List<Integer>> combos = new ArrayList<>();        combinations(4, 2, 1, new ArrayList<>(), combos);        System.out.println(combos.size() + " " + combos);        List<List<Integer>> few = new ArrayList<>();        combinations(3, 0, 1, new ArrayList<>(), few);        System.out.println(few);    }}

6 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]6 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]][[]]

The permutation order comes from the order of the loop. In the first few steps: pick 1, then from {2, 3} pick 2, then 3: [1, 2, 3] is recorded. Backtrack: unpick 3, unpick 2, pick 3 instead, then 2: [1, 3, 2]. And so on. The used array is what lets us "unpick" cleanly.

Complexity. There are n! permutations, each costing O(n) to copy: time O(n × n!). Depth n, so extra space O(n) beyond the output. For combinations, there are C(n, k) results, each of length k, so time O(k × C(n, k)).

Pruning matters here. Without the bound, the loop would also start branches that can never reach size k, wasting work. For subsets, permutations and combinations, the number of results is the real cost: if the output is exponential, no method can do better than exponential time.

Problem. Place n queens on an n × n chessboard so that no two attack each other (no two share a row, a column or a diagonal). Count the arrangements.

Search. Place one queen per row, row by row. In each row, try every column. A square is allowed only if no earlier queen shares its column or either diagonal. If no column works for some row, we have a dead end, so return to the previous row and try its next column. This is backtracking with pruning at every step.

To check attacks in O(1), notice that:

• all squares on the same / diagonal share the same row + col;
• all squares on the same \ diagonal share the same row - col (we add n - 1 to avoid negative indexes).

So three boolean arrays are enough: cols, diag1 (indexed by row + col) and diag2 (indexed by row - col + n - 1).

// File: Main.javapublic class Main {    static int countSolutions(int n) {        return place(0, n, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);    }    static int place(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {        if (row == n) {            return 1;                                       // all queens placed        }        int count = 0;        for (int col = 0; col < n; col++) {            int d1 = row + col;            int d2 = row - col + n - 1;            if (cols[col] || diag1[d1] || diag2[d2]) {                continue;                                   // attacked: prune this square            }            cols[col] = true;                               // choose            diag1[d1] = true;            diag2[d2] = true;            count += place(row + 1, n, cols, diag1, diag2); // explore            cols[col] = false;                              // undo            diag1[d1] = false;            diag2[d2] = false;        }        return count;    }    // Finds the first solution in the same search order, or null if none exists.    static int[] firstSolution(int n) {        int[] queenColumn = new int[n];        boolean found = search(0, n, queenColumn, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);        return found ? queenColumn : null;    }    static boolean search(int row, int n, int[] queenColumn, boolean[] cols, boolean[] diag1, boolean[] diag2) {        if (row == n) {            return true;        }        for (int col = 0; col < n; col++) {            int d1 = row + col;            int d2 = row - col + n - 1;            if (cols[col] || diag1[d1] || diag2[d2]) {                continue;            }            cols[col] = true;            diag1[d1] = true;            diag2[d2] = true;            queenColumn[row] = col;            if (search(row + 1, n, queenColumn, cols, diag1, diag2)) {                return true;                                // stop at the first solution            }            cols[col] = false;            diag1[d1] = false;            diag2[d2] = false;        }        return false;    }    public static void main(String[] args) {        StringBuilder counts = new StringBuilder();        for (int n = 1; n <= 8; n++) {            counts.append("n=").append(n).append(": ").append(countSolutions(n)).append("  ");        }        System.out.println(counts.toString().trim());        int[] solution = firstSolution(4);        for (int row = 0; row < 4; row++) {            StringBuilder line = new StringBuilder();            for (int col = 0; col < 4; col++) {                line.append(solution[row] == col ? 'Q' : '.');            }            System.out.println(line);        }        System.out.println(firstSolution(3) == null);    }}

n=1: 1  n=2: 0  n=3: 0  n=4: 2  n=5: 10  n=6: 4  n=7: 40  n=8: 92.Q.....QQ.....Q.true

There are no solutions for n = 2 or n = 3, two for n = 4, and 92 for n = 8. Each queen's row is fixed (one per row), so we only choose columns. That alone cuts the search enormously: instead of choosing 8 squares from 64, we choose one column per row.

Complexity. The worst case is exponential, loosely O(n!), because each row has at most n choices and the number of choices shrinks as queens are placed. Pruning makes it far faster than that in practice. Time does not shrink to polynomial, but pruning keeps it practical: n = 12 (14,200 solutions) took about 55 milliseconds on the machine we tried it on. Space is O(n) for the arrays and the recursion.

Look for these signals:

• "Return all ..." (all subsets, all orderings, all valid strings).
• "Is there any way to ..." with many combinations to try.
• The input is small (usually n up to about 10 to 20), because the answer count is exponential.
• You build the answer step by step and each step has a few options.
• Some partial answers can be rejected early.

If the problem asks for a count or an optimum and there is repeated work in the tree (like fib(2) appearing twice), dynamic programming is usually the better tool. We study it in Dynamic Programming Foundations.

• No base case, or a base case that is never reached. This ends in StackOverflowError.
• A recursive call that does not make the problem smaller. For example f(n) calling f(n).
• Forgetting to undo the choice. State from one branch leaks into the next and produces wrong results.
• Saving a reference instead of a copy (result.add(current)). Always new ArrayList<>(current).
• Mixing up remove(int index) and remove(Object value) on a List<Integer>.
• Duplicate input values causing duplicate answers. Sort and skip repeated values at the same level.
• Overflow in recursive arithmetic. factorial(21) and power(2, 63) exceed a long.
• Recursing too deeply. More than several thousand levels is risky. Use a loop or an explicit stack.
• Shared mutable state. If your recursion uses fields or arrays, make sure each call restores them exactly.
• Not thinking about the size of the output. If the answer has 2^n items, an n of 30 means over a billion results.

static String g(int n) {    if (n == 0) {        return "";    }    return g(n / 2) + (n % 2);}

static void subsetsBuggy(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {    result.add(current);    for (int i = start; i < nums.length; i++) {        current.add(nums[i]);        subsetsBuggy(nums, i + 1, current, result);    }}

// File: Main.javapublic class Main {    static String g(int n) {        if (n == 0) {            return "";        }        return g(n / 2) + (n % 2);    }    static String toBinary(int n) {        return n == 0 ? "0" : g(n);    }    public static void main(String[] args) {        System.out.println("[" + g(6) + "] [" + g(10) + "] [" + g(0) + "] [" + g(1) + "]");        System.out.println(toBinary(0) + " " + toBinary(6) + " " + Integer.toBinaryString(10));    }}

[110] [1010] [] [1]0 110 1010

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static void build(int n, StringBuilder current, List<String> result) {        if (current.length() == n) {            result.add(current.toString());            return;        }        current.append('0');                                  // 0 is always allowed        build(n, current, result);        current.deleteCharAt(current.length() - 1);        boolean previousIsOne = current.length() > 0 && current.charAt(current.length() - 1) == '1';        if (!previousIsOne) {                                  // 1 only after a 0 or at the start            current.append('1');            build(n, current, result);            current.deleteCharAt(current.length() - 1);        }    }    static List<String> noAdjacentOnes(int n) {        List<String> result = new ArrayList<>();        build(n, new StringBuilder(), result);        return result;    }    public static void main(String[] args) {        System.out.println(noAdjacentOnes(3));        System.out.println(noAdjacentOnes(1));        System.out.println(noAdjacentOnes(0));        System.out.println(noAdjacentOnes(4).size() + " " + noAdjacentOnes(5).size());    }}

[000, 001, 010, 100, 101][0, 1][]8 13

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static void generate(int n, int open, int close, StringBuilder current, List<String> result) {        if (current.length() == 2 * n) {            result.add(current.toString());            return;        }        if (open < n) {            current.append('(');            generate(n, open + 1, close, current, result);            current.deleteCharAt(current.length() - 1);        }        if (close < open) {            current.append(')');            generate(n, open, close + 1, current, result);            current.deleteCharAt(current.length() - 1);        }    }    static List<String> generateParentheses(int n) {        List<String> result = new ArrayList<>();        generate(n, 0, 0, new StringBuilder(), result);        return result;    }    public static void main(String[] args) {        System.out.println(generateParentheses(3));        System.out.println(generateParentheses(1));        System.out.println(generateParentheses(0));        for (int n = 1; n <= 5; n++) {            System.out.print(generateParentheses(n).size() + " ");        }        System.out.println();    }}

[((())), (()()), (())(), ()(()), ()()()][()][]1 2 5 14 42

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static void subsetsBuggy(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {        result.add(current);        for (int i = start; i < nums.length; i++) {            current.add(nums[i]);            subsetsBuggy(nums, i + 1, current, result);        }    }    static void subsetsFixed(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {        result.add(new ArrayList<>(current));        for (int i = start; i < nums.length; i++) {            current.add(nums[i]);            subsetsFixed(nums, i + 1, current, result);            current.remove(current.size() - 1);        }    }    public static void main(String[] args) {        List<List<Integer>> buggy = new ArrayList<>();        subsetsBuggy(new int[] {1, 2}, 0, new ArrayList<>(), buggy);        System.out.println(buggy);        List<List<Integer>> fixed = new ArrayList<>();        subsetsFixed(new int[] {1, 2}, 0, new ArrayList<>(), fixed);        System.out.println(fixed);    }}

[[1, 2, 2], [1, 2, 2], [1, 2, 2], [1, 2, 2]][[], [1], [1, 2], [2]]

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main {    static void search(int[] sorted, int start, int remaining, List<Integer> current, List<List<Integer>> result) {        if (remaining == 0) {            result.add(new ArrayList<>(current));            return;        }        for (int i = start; i < sorted.length; i++) {            if (sorted[i] > remaining) {                break;                                      // sorted, so all later ones are too big too            }            current.add(sorted[i]);                         // choose            search(sorted, i, remaining - sorted[i], current, result);   // i, not i + 1: reuse allowed            current.remove(current.size() - 1);             // undo        }    }    static List<List<Integer>> combinationSum(int[] candidates, int target) {        int[] sorted = candidates.clone();        Arrays.sort(sorted);        List<List<Integer>> result = new ArrayList<>();        search(sorted, 0, target, new ArrayList<>(), result);        return result;    }    public static void main(String[] args) {        System.out.println(combinationSum(new int[] {2, 3, 6, 7}, 7));        System.out.println(combinationSum(new int[] {2, 3, 5}, 8));        System.out.println(combinationSum(new int[] {2}, 1));        System.out.println(combinationSum(new int[] {2, 3}, 6));        System.out.println(combinationSum(new int[] {}, 4));    }}

[[2, 2, 3], [7]][[2, 2, 2, 2], [2, 3, 3], [3, 5]][][[2, 2, 2], [3, 3]][]

• Next: Trees and Binary Search Trees. A tree is a recursive structure: every subtree is a smaller tree. Everything in this article applies directly.
• Later: Searching and Sorting uses recursion for merge sort and quick sort, and Dynamic Programming Foundations shows how to remove the repeated work from recursion.
• Practice habit: when you write a recursive method, first write one comment for the base case and one for the recursive step, in plain English, before you write any code.