Week 7 - Recursion
Schedule an appointment now to take your final. See the discussion board for details.
Learning objectives
Upon finishing this week, you should be able to:
- Trace recursive algorithms by hand
- Write recursive algorithms to solve problems
Suggested pacing
Monday
- Recursion concepts
- Do Recursion Practice WS (See classroom files link)
Tuesday
- Recursion writing
- Do Recursion 1 CPPLab
Wednesday
- Recursion Applications
- Do Recursion 2 CPPLab
Thursday
- Work on assignment 7
Friday
- BigO review and classification of vector operations
Recursion Basics
Read 17.1-17.2. Watch this video:
Do the Recursion Practice WS from classroom files link. The key is there as well.
Recursion writing and helper functions
Read 17.3-17.5 and watch these two videos:
Do Recursion 1 CPPLab
Applications of Recursion
Read 17.6-17.9 and watch this video (hint: the flood fill sample is very similar to the logic you need for assignment 8). Source code is in the Github repository
Big-O
Review Big O in Welcome to CS chapter 8.10 and 8.12 and/or Liang Ch 18.2.
This video reviews the core ideas:
Then watch these videos that cover the efficiency of various array-based list algorithms:
Asking VS Code to run a program for you (Run button or F5) can sometimes introduce unpredictable
overhead. For accurate and repeatable results, you should always do timing by
running your program by hand from the terminal.