CS 5010 Module 08

Module Overview

In some problems, the pattern of recursion does not fit into our strategy of structural decomposition, even with invariants, because we need to recur on quantities that are not pieces of the input structure. In this module, you will see some examples of problems that do not fit into the pattern of structural recursion, and you will learn about the strategy of "general recursion", which is capable of solving these problems.

Course Map

Readings

Part V from the textbook.

Resources

• Examples for Week 08
• Problem Set 06 Debriefing and In-class Coding Exercise for Tues 325pm section
• Problem Set 06 Debriefing and In-class Coding Exercise for Tues 600pm section
• Problem Set 06 Debriefing and In-class Coding Exercise for Wed 600pm section

Lessons and Guided Practices

• Lesson 8.1 Sometimes Structural Recursion Isn't Enough
• Guided Practice 8.1
• Lesson 8.2 Introducing General Recursion
• Guided Practice 8.2
• Lesson 8.3 Binary Search
• Guided Practice 8.3
• Lesson 8.4 Searching in a Graph
• Guided Practice 8.4

Problem Set

Problem Set 07