Meeting 06: Recursion Part II

Today we will continue our discussion of recursion. We will look at two more examples

• Binary search of arrays
• Towers of Hanoi solution

Then we will discuss performance issues with recursion and discuss when and how to convert a recursive solution to an iterative one.

Links

• Slides
• Exercise Starter Code

In-class Exercise: Binary Search

Lets implement the binary search algorithm operating on a std::array.

1. Download the starter code
2. In search.hpp implement the recursive binary search algorithm as defined.
3. In search.hpp implement the iterative binary search algorithm as defined.
4. Build your code locally as you work. Use the provided set of Catch tests.
5. Submit your search.hpp file via Canvas at the Assignment "Exercise for Meeting 6".