chapter fifteen

15 Designing solutions with recursion and backtracking

 

This chapter covers

  • Recursion for designing solutions to programming problems
  • Dynamic backtracking to try different solution paths during run time

Recursion is a software design technique that we can use to create solutions to certain programming problems. It involves a function or method 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, we can design solutions that may be difficult 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

15.2 Finding the largest value of a list by recursion

15.3 Reversing a list 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.6 Quicksort a list with recursion

15.6.1 Quicksort in action

15.6.2 Partitioning a list into sublists

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