15 Designing solutions with recursion and backtracking

This chapter presents recursion as a core software design technique and shows how pairing it with dynamic backtracking expands its power for search and constraint problems. Recursion tackles a task by reducing it to smaller, similar subproblems until hitting a base case, then “unwinding” results to solve the original problem. The chapter demystifies how recursive calls correspond to a loop’s initialization, iteration, and termination, stresses the need to shrink state toward a base case to avoid infinite recursion, and cautions that misuse can cause significant performance issues.

To ground the concepts, the text first uses simple demonstrations (finding the maximum in a list and reversing a list) to make base cases and recursive steps concrete, then highlights a classic fit for recursion with the Towers of Hanoi. It extends the idea to recursively defined data structures by implementing binary search tree operations—recursive insertion and inorder traversal for sorted output. The chapter then develops quicksort: choose a pivot, partition the list into two regions around it, and recursively sort the sublists, with small-size base cases ensuring progress and the pivot landing in its final position after each partition.

The chapter closes with both a warning and an upgrade in technique. It shows how a direct recursive implementation of the Fibonacci sequence explodes exponentially due to repeated subcalls, underlining the importance of understanding call counts, base cases, and recursion limits. It then introduces dynamic backtracking to explore decision trees efficiently: the eight queens puzzle is solved column by column by placing non-attacking queens and backtracking when stuck, and Sudoku is solved cell by cell by trying allowable numbers (respecting row, column, and block constraints) and backtracking on failure. Together, these patterns illustrate when recursion is elegant and effective and how backtracking turns it into a practical solver for complex search problems.

How the recursive function largest() finds the largest value in a list. The boxed values are the ever-shortening list arguments of the calls. The return value of each recursive call enables the caller to return its value.

How the recursive function reverse() reverses the contents of a list. Each call removes the first value, recursively reverses the rest of the list, and then appends the removed first value to the end.

The starting and ending positions of four disks in the Towers of Hanoi puzzle. We moved the disks from source pin L to destination pin R.

A conceptual solution with four disks that uses pin M as the temporary pin.

The base case of moving a single disk from pin L to pin R. No recursion needed.

The sequence of moves to get two disks from pin L to pin R using pin M as the temporary pin.

The sequence of moves to get three disks from pin L to pin R. During the steps, the pins change source, destination, and temporary pin roles.

A binary tree, where each nonempty node has zero, one, or two child nodes that are roots of subtrees. Each subtree is itself a binary tree, so a binary tree is recursively defined. This binary tree is also a binary search tree (BST), where at each nonempty parent node, values in the left child subtree are less than or equal to the parent node’s value, and values in the right subtree are greater. Each subtree is itself a BST, and so a BST is recursively defined.

The values were inserted into this BST in the order 42, 30, 5, 35, 63, 75, 25, 51, 44, 19, and 55. To insert the new value 60 into the tree, private method _insert() is called recursively until it reaches a base case of an empty subtree. The new node replaces the empty subtree, and the value is thereby inserted into the tree at its proper place.

Recursively printing the values of a BST in sorted order. At each parent node, first recursively print the values in its left child subtree if one exists, next print the parent node’s value, and then recursively print the values in the parent node’s right child subtree if one exists. The small numbers next to each node indicate the order that the nodes are printed.

The quicksort algorithm in action as it sorts a list. The circled values are the chosen pivot elements that create the sublists on both sides after partitioning. The rectangles enclose the sublists to be quicksorted recursively. In each line, the shaded sublist is the one actively being sorted. The values in bold are already in their correct places in the final sorted list. Note that the chosen pivot elements are always already in their correct places after partitioning.

Choosing 52 (circled) to be the pivot value and then partitioning the list into two sublists. Variables i and j are list indexes. After partitioning, all values to the left of 52 are less or equal, and all values to the right of 52 are greater. The two boxed sublists on either side of the pivot are now ready to be recursively quicksorted.

The tree of recursive calls to compute f(6). There are already many repeated calls with the same arguments. To compute f(n) as n becomes greater, the tree will grow larger, and the computation will take exponentially longer.

A decision tree showing recursion to move from one stage to the next and backtracking to try other paths in earlier stages.

• Recursion is a software design technique that solves a problem by repeatedly dividing it into a smaller and smaller but similar subproblems. We recursively solve each subproblem the same way.
• The recursion stops at a base case where the subproblem is so small that it has an obvious and immediate solution. Then the original problem is solved as the recursion unwinds.
• When designed properly, a recursive programming solution can be simple and elegant. But improper use can lead to serious performance problems.
• The combination of recursion and dynamic backtracking is a potent design tool for programs that explore multiple solution paths.
• Each step can have multiple solution paths that are explored using recursion. After trying a path, backtrack and try the next path.
• When all the solution paths at a step have been tried, backtrack to the previous step, and continue trying the previous step’s paths.
• When we’ve backtracked to the starting step, either we found all the solutions, or we discovered that the problem is unsolvable.

FAQ