Thinking Recursively in Python: Overview
A lot of real-world problems can be broken down into smaller variations of themselves, so you can use recursion to solve them. You’ll see how you can use iteration and then recursion to help Santa Claus deliver presents.
Iterative solution
Santa Claus goes to each house, delivers the presents, and continues on to the next house:
houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]
def deliver_presents_iteratively():
for house in houses:
print("Delivering presents to", house)
Recursive solution
Santa Claus designates all the work to one elf. That elf follows these rules:
- If they are responsible for more than 1 house, then they are a manager and split their workload between two elves, who then follow these same rules.
- If the elf is responsible for only 1 house, then they are a worker and deliver the presents to that house.
You’ll go through the code for this solution in the third lesson in this course.
To download the code in this course, click the link below:
To download the slides in this course, click the link below:
00:00 Hi, my name is James, and today we’ll be talking about recursion. First we’ll go over “Why recursion?” and how it applies to the real world. Then we’ll talk about defining a recursive function.
00:11 We’ll go through some examples. We’ll talk about maintaining state in our recursive functions. We’ll talk about some optimizations and some pesky details.
00:21 So, why recursion? Well, problems in computer science and in life can sometimes be scary and intimidating. We naturally break down problems into smaller subproblems.
00:32 If one of our subproblems—or one or more, I should say—is a variation of our larger problem, then we can solve it recursively. So the big picture idea here is if our problem can be broken down into smaller versions of itself, then that’s when we use recursion to solve those problems.
00:51 For example, if we want to read a book recursively, we’d break it down into two subproblems: one, reading page one today, and the second subproblem being reading the rest starting tomorrow.
01:03 Notice how the second subproblem is actually a smaller version of our larger problem, because a book is defined to be a collection of pages and reading the rest of the book is actually reading just a smaller version of the book.
01:17 Creating this video is not recursive because I broke it down into two subproblems—recording the video and editing the video—and neither of those are a smaller version of our big problem of creating a video. Before we get into an example, let’s talk about a iterative solution to a real-world problem, and then we’ll talk about how to solve it recursively.
01:40
So, how does Santa Claus deliver Christmas presents? Well, he goes to each house and delivers the presents. That’s a very natural, iterative solution. We have a list of houses, we define deliver_presents_iteratively(), we loop through the houses, and then we print("Delivering presents to", house).
01:59 Now we want to use recursion. Santa Claus is getting old, so he can’t do this himself. Let’s see if we can break the larger problem into smaller recursive subproblems. What I mean by that is let’s break the problem of delivering presents to all the houses into smaller subproblems, which are just delivering presents to some of the houses. Well, how are we going to do that? Well, let’s first give all the work to the elf—that’s not really part of the solution, that’s just saying if Santa Claus has to deliver to four houses, now this elf has to deliver to four houses.
02:29 But here’s where the recursive solution comes into play.
02:33 We assign titles and responsibilities to the elves based on the number of houses for which they’re responsible.
02:40 That means if a elf is responsible for more than one house, they are a manager and they just appoint two elves to divide the work among them. So if this elf is in charge of four houses, now they just say, “Oh, these two elves are in charge of two houses each.” Those two elves, who are in charge of two houses each, say they’re a manager, so they say, “Okay, two more elves.
03:03 They’re in charge of one house each.” Well, what happens when they get to one house? They are not a manager anymore, they are a worker, and they have to deliver the presents.
03:13 Notice how we broke the larger problem in half, pretty much. We had four houses and then that got broken into two subproblems of two houses each. Here’s a visual that might help us.
03:27 We have Elf 1 that delivers to four houses, and then they appoint two elves to deliver to two houses each, and those elves appoint one elf to deliver to one house each, and then those elves are the ones that actually deliver the presents.
03:44 Here we have broken down the problem of delivering to four houses into two subproblems. Those subproblems got broken into two more subproblems each, et cetera, et cetera, building this sort of tree structure that is very common in recursion where your initial breaking down of subproblems gets broken down into subproblems themselves and keeps getting broken down into subproblems until you hit some sort of end point. We’ll talk through the actual code once we go over how to define a recursive function and some other simpler examples.
Become a Member to join the conversation.