Recursion
Prev: Binary Search Trees (BSTs) Next: Dynamic Programming
Problems
16.1
A peg contains rings in sorted order, with the largest at the bottom. You are to transfer these rings to another peg, initially empty. The only permitted move is to take a single ring from the top of one peg and place it on the top of another peg. You may never place a larger ring above a smaller ring.
Write a program that prints a sequence of operations that transfers n rings from one peg to another.
Hint: If you know how to transfer the top n - 1 rings, how does that help with the nth ring?
Variant: Solve the same problem without using recursion.
Variant: Find the minimum number of operations subject to the constraint that each operation must involve P3.
Variant: Find the minimum number of operations subject to the constraint that each transfer must be from P1 to P2, P2 to P3, or P3 to P1.
Variant: Find the minimum number of operations subject to the constraint that a ring can never be transferred directly from P1 to P2 (transfers from P2 to P1 are allowed).
Variant: Find the minimum number of operations when the stacking constraint is relaxed so that the largest ring on a peg must be the lowest ring on the peg. The remaining rings on the peg can be in any order.
Variant: You have 2n disks of n different sizes, two of each size. You cannot place a larger disk on a smaller disk, but you can place a disk of equal size on top of the other. Compute the minimum number of moves to transfer the 2n disks from P1 to P2.
Variant: You have 2n disks colored black or white. You cannot place a white disk directly on top of a black disk. Compute the minimum number of moves to transfer the 2n disks from P1 to P2.
Variant: Find the minimum number of operations if you have a fourth peg, P4.
16.2
A nonattacking placement of queens is one in which no two queens are in the same row, column, or diagonal.
Write a program that returns all distinct nonattacking placements of n queens on an n × n chessboard.
Hint: If the first queen is placed at (i, j), where can the remaining queens definitely not be placed?
Variant: Compute the number of nonattacking placements of n queens on an n × n chessboard.
Variant: Compute the smallest number of queens that can be placed to attack each uncovered square.
Variant: Compute a placement of 32 knights, or 14 bishops, 16 kings, or 8 rooks on an 8 × 8 chessboard in which no two pieces attack each other.
16.3
This problem is concerned with computing all permutations of an array. For example, if the array is (2,3,5,7) then one valid output ordering is (2,3,5,7), (2,3,7,5), (2,5,3,7), ..., and any ordering of all permutations is acceptable.
Write a program that takes as input an array of distinct integers and generates all permutations of that array. No permutation may appear more than once.
Hint: How many possible values are there for the first element?
Variant: Solve the same problem when the input array may have duplicates. Do not repeat any output permutation.
16.4
The power set of a set S is the set of all subsets of S, including the empty set and S itself.
Write a function that takes as input a set and returns its power set.
Hint: There are 2^n subsets of a set of size n. There are 2^n n-bit words.
Variant: Solve the problem when the input array may have duplicates, i.e., denotes a multiset. You should not repeat any output multiset.
16.5
There are applications in testing that require computing all subsets of a fixed size.
Write a program that computes all size-k subsets of {1, 2, ..., n}, where k and n are inputs. For example, if k = 2 and n = 5, the result is {{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}}.
Hint: Think about the right function signature.
16.6
Strings in which parentheses are matched are defined by these rules:
- The empty string is a string with matched parentheses.
- Adding a leading left parenthesis and a trailing right parenthesis to a string with matched parentheses yields another string with matched parentheses.
- The concatenation of two strings with matched parentheses is itself a string with matched parentheses.
For example, the strings containing two pairs of matched parentheses are (()) and ()(), and those with three pairs are ((())), (()()), (())(), ()(()), and ()()().
Write a program that takes as input a number and returns all strings with that number of matched pairs of parentheses.
Hint: Think about what the prefix of a string of matched parentheses must look like.
16.7
A string is palindromic if it reads the same backwards and forwards. A decomposition of a string is a sequence of strings whose concatenation is the original string.
Compute all palindromic decompositions of a given string. For example, if the string is "0204451881", then "020", "44", "5", "1881" is a valid decomposition, as is "020", "44", "5", "1", "88", "1". However, "02044", "5", "1881" is not valid because "02044" is not a palindrome.
Hint: Focus on the first palindromic string in a decomposition.
16.8
Write a program that returns all distinct binary trees with a specified number of nodes. For example, if the number of nodes is three, return the five binary trees shown in Figure 16.5.
Hint: Can two binary trees whose left subtrees differ in size be the same?
16.9
Implement a Sudoku solver. See Problem 6.16 on Page 84 for a definition of Sudoku.
Hint: Apply the constraints to speed up a brute-force algorithm.
16.10
An n-bit Gray code is a permutation of {0, 1, 2, ..., 2^n - 1} such that the binary representations of successive entries differ in only one place. The first and last entries must also differ in only one place. For example, for n = 3, 000, 001, 011, 010, 110, 111, 101, 100 is a Gray code.
Write a program that takes n as input and returns an n-bit Gray code.
Hint: Write out Gray codes for n = 2, 3, 4.
16.11
Packets in Ethernet local area networks are routed according to the unique path in a tree whose leaves correspond to clients, internal nodes to switches, and edges to physical connections. The diameter of a tree is the length of a longest path in the tree.
Figure 16.6 illustrates the concept. Design an efficient algorithm to compute the diameter of a tree.
Hint: The longest path may or may not pass through the root.
Variant: Consider a computer network organized as a rooted tree. A node can send a message to only one child at a time, and it takes one second for the child to receive the message. The root has complete knowledge of the tree and needs to send this message to all nodes. Design an algorithm that computes the sequence of transfers that minimizes the total broadcast time.
Answers
16.1
Use the standard recursive decomposition: move the top n - 1 rings to the spare peg, move the largest ring to the destination, then move the n - 1 rings from the spare peg onto it. This yields the recurrence T(n) = 2T(n - 1) + 1, so the number of moves is 2^n - 1.
16.2
Build the placement row by row. Keep a partial array where entry i is the column chosen for row i, and only recurse on placements that do not conflict by column or diagonal with earlier rows. This is the standard backtracking solution.
16.3
Generate permutations by fixing each possible value in the current position, swapping it into place, recursively generating all permutations of the suffix, and then swapping back. This enumerates all n! permutations without duplicates when the input elements are distinct.
16.4
Recursively decide, for each element, whether it is included in the current subset or not. Equivalently, enumerate the 2^n bitmasks and interpret set bits as selected elements. Both approaches generate the full power set.
16.5
Generate combinations incrementally with a partial subset and the next candidate value. At each step choose the next element from a range that leaves enough values to complete a size-k subset, recurse, and then backtrack. The output size is \binom{n}{k}, which dominates the running time.
16.6
Construct valid strings directly instead of filtering arbitrary strings. Track how many left and right parentheses remain to be placed, only add '(' when some are left, and only add ')' when it will not make the prefix invalid, i.e., when more right parentheses remain than left. This enumerates exactly the balanced strings.
16.7
Recursively choose a palindromic prefix, append it to the current decomposition, and recurse on the remaining suffix. Backtrack after each recursive call. This prunes large parts of the naive search because non-palindromic prefixes are never extended.
16.8
For each possible split of n - 1 remaining nodes into a left-subtree size and a right-subtree size, recursively generate all left and right subtrees of those sizes and combine every pair under a new root. This produces all structurally distinct binary trees. The counts follow the Catalan numbers.
16.9
Use backtracking on the grid. Find an empty cell, try each feasible digit, and recurse only if the placement preserves the row, column, and subgrid constraints. Undo the choice on failure. Constraint checking prunes the brute-force search enough to make the solver practical.
16.10
One approach is backtracking over unused codewords, always appending a value that differs by one bit from the previous value and ensuring the final value also differs by one bit from the first. A cleaner recursive construction is reflection: prepend 0 to an (n - 1)-bit Gray code, then prepend 1 to its reverse. This gives O(2^n) output-sensitive time.
16.11
Compute, for each node, the height of its deepest descendant path and the best diameter within its subtrees. The diameter through a node is the sum of its two largest child-rooted path lengths, while the overall diameter is the maximum of that value and all subtree diameters. A single postorder traversal gives O(n) time.