Week 9 - Recursion and BigO Intro

Learning objectives

Upon finishing this week, you should be able to:

• Trace recursive algorithms by hand
• Write recursive algorithms

Suggested pacing

Day 1

• Recursion Basics (Ch 24.1-24.4)
• Do Recursion Practice WS

Day 2

• Recursion Design (Ch 24.5-24.8)
• Start Ch 24 Exercises 1 and 2 (Remember it is better to do part of each set rather than all of one and none of the other)

Day 3

• Advanced Recursion (Ch 24.9-24.12)
• Continue Ch 24 Exercises 1 and 2

Day 4

• BigO Basics
• Check out assignment

Activity Outline

Recursion Basics

Read Ch 24.1-24.4

Do the Recursion Practice WS. It and a key are available in Canvas.

This optional video reviews the basics of recursion:

And this brief one explains why we need recursion:

Recursion Design

Read Ch 24.5-24.8

Work on the two exercise sets for Ch 24. The second exercise set focus on using vectors and does not depend on the first one. You will likely find it easier than some of the problems in the first set, so if you get stuck on the first set, you can switch to the second one and come back to the first one later.

This optional video covers the basics of designing of recursive algorithms:

While this one covers using extra parameters to maintain state in recursive algorithms:

Advanced Recursion

Read Ch 24.9-24.12.

This optional video covers tail recursion:

And this one covers recursive algorithms that make multiple recursive calls:

Big-O

Read Ch 25.1-25.3 and 25.5 (ignore 25.4 for now)

This video reviews the core ideas: