15 Designing solutions with recursion and backtracking

Recursion is a software design technique that we can use to create solutions to certain programming problems. It involves a function that calls itself, and nearly all modern programming languages support this important technique. If we use recursion properly with certain classes of programming problems, we can design solutions that are simple and elegant — and some might claim magical. With recursion, can design solutions that may be difficult to solve otherwise.

Recursion requires a different way of thinking about how to design a programming solution to a problem. Unfortunately, for some programmers, it is too mysterious and forbidding to use. This chapter clears away the mystery and demonstrates how combining recursion with dynamic backtracking gives us even more powerful design tools. But we’ll also see how misusing recursion can cause surprising performance disasters. With experience, we can learn when it is appropriate to design with recursion.

15.1 Recursion compared to the for loop

We can remove some of the mystery behind recursion by comparing it to the familiar for loop.

15.2 Finding the largest value by recursion

15.3 Reversing a vector by recursion

15.4 Solve the Towers of Hanoi puzzle by recursion

15.5 Recursive algorithms for a binary search tree

15.5.1 Inserting into a BST with recursion

15.5.2 Printing a BST with recursion

15.5.3 Removing all the nodes of a BST with recursion

15.6 Quicksort an array with recursion

15.6.1 Quicksort in action

15.6.2 Partitioning an array into subarrays

15.6.3 Quicksort implementation

15.7 The Fibonacci sequence and a recursion disaster

15.8 Dynamic backtracking increases the power of recursion

15.9 Solving the eight queens puzzle with recursion and backtracking

15.10 Solving Sudoku puzzles with recursion and backtracking

15.11 Summary