Date: July 06
Recursion is a powerful tool that allows us to express the “solution” to a problem in terms of a “base step” and a “recursive step.” Essentially, it’s a programming tool that can make it really easy to break seemingly large problems down into simple steps. It is not exclusive to ISL+ or to functional programming. It exists in almost all programming languages as it’s often the simplest way to express a solution to complex problems.
For example, here it is in Python!
While it is powerful…it is also confusing. We have to get used to thinking in this new way in order for it to be useful to us as computer scientists.
If you’re bored, try googling “recursion” and seeing what happens! No mini-quiz as I’d rather you spend your time working on the tutorials and exercises this week.
In-Class Resources
| Link | Title | Type | Duration |
|---|---|---|---|
| Video 1 | Lecture 9.1 - Introduction | pre-recorded | 4:47 |
| Video 2 | Lecture 9.2 - Motivating Recursion | pre-recorded | 7:56 |
| Video 3 | Lecture 9.3 - Writing Recursive Functions | pre-recorded | 10:00 |
| Video 4 | Lecture 9.4 - Writing foldl/r | pre-recorded | 3:37 |
| Video 5 | Lecture 9.5 - Writing length | pre-recorded | 5:36 |
| Video 6 | Lecture 9.6 - Writing Iterated Beside and Sussman Form | pre-recorded | 7:12 |
| Video 7 | Execution is Recursive! (Bonus) | pre-recorded | 1:55 |