Topic 3. Recursion

Lectures

• Lecture 6. Thinking Recursively, Part I

  Recursion is a powerful tool for problem-solving. This lecture explores how to use recursion to generate and display intricate graphics in a surprisingly small space.

  • Readings: Chapter 8.1, Chapter 8.4

  • Code

• Lecture 7. Thinking Recursively, Part II

  This lecture explores recursion through the lens of decision trees, as well as how to generate all subsets of a set.

  • Readings: Chapter 8.2, Chapter 8.3

  • Code

• Lecture 8. Thinking Recursively, Part III

  Recursion and iteration are not mutually exclusive. This lecture shows how to tie them together in the context of graphics and listing permutations.

  • Code

• Lecture 9. Thinking Recursively, Part IV

  This lecture continues exploring recursive enumeration through combinations, then switch from asking “list all ways to do X” to “is there a way to do X?”

  • Readings: Chapter 9.1 - 9.2

  • Code

• Lecture 10. Thinking Recursively, Part V

  This lecture explores recursive backtracking in more depth and how to use it to find solutions to a variety of word puzzles.

  • Code

Sections

• Section 3.1 Recursion Iteration Backtracking

• Section 3.2 More Backtracking

Assignments

• Assignment 3.1 A Visit to Recursia

• Assignment 3.2 Recursion to the Rescue