Multiple Recursive Calls

Thinking Recursively With Python James Uejio 04:12

In this lesson, you’ll go over the code for the recursive solution to the Santa Claus problem from the first lesson:

Python
      
    
def deliver_presents_recursively(houses):
    if len(houses) == 1:
        print("Delivering presents to", houses[0])
    else:
        mid = len(houses) // 2
        first_half = houses[:mid]
        second_half = houses[mid:]

        # first elf
        deliver_presents_recursively(first_half)
        # second elf
        deliver_presents_recursively(second_half)

00:00 Now that we know how to define a recursive function, let’s revisit the Santa recursive algorithm. Let’s define deliver_presents_recursively(), taking our houses, and then let’s start with the recursive case.

00:16 So remember that our elf splits their work into two. So imagining that the length of the houses is greater than 1, if len(houses) > 1: then we have to find the middle point, which is the length of our houses, floordiv 2, and then let’s split our houses in half.

00:43 Remember that list slicing creates a copy of the houses between this index and this index, not including this index. So here we have… The first half would be houses up until mid, which in our case, this would be 4 // 2, which is 2.

01:06 This would include the value at the zeroth index and the first index, and then the second half would include the second index and third index. And then remember that our elf splits their work into two elves, so # first elf—what does the first elf do? Well, the first elf just delivers the presents to the first half of the houses, and then the second elf, # second elf,

01:34 delivers to second_half. Oops.

01:41 Okay, so let’s save it. Let’s run it. deliver_presents_recursively(houses). Okay, nothing got outputted. Why was that? Well, we recursed correctly, where we cut our houses in halves and then in halves and then in halves.

01:59 But what happened when we reached houses is only one link, or when we only have one house? Well, it didn’t enter the if case. It went down here and remember that if there is no explicit return statement, functions will return None. So it just returned None, so we outputted None.

02:18 So we need a case here, an else case, where we need to print "Delivering presents to "—who? houses[0], because we can assume that the length of the houses will be 1, and so we’ll get the first value of the house and that will print "Delivering presents to " that house. Let’s exit, load, perfect. A extra space, but that’s okay.

02:53 Cool! So this was the same output as deliver_presents_iteratively().

03:01 Nice. So, before we’re done with this code, let’s clean it up a little bit. It’s a little bit more orthodox in a recursive function to have the base case on top, so that way it’s clear what the simplest version of the problem is right from the get-go. And then we put all this in the else.

03:26 Let’s go like this, like that. Let’s save, let’s just double-check.

03:33 Nice. Let’s look at how the recursive calls worked. We first called it on the four houses and then we called it on the two houses and then we called it on the one. That printed out “Delivering to the first house”. Then we went on to the second house.

03:52 Then we went on to the right side now, and that called it on that house, and then this house. So that’s very common for a recursive function that has multiple recursive calls to first evaluate all of the first recursive call before moving on to the second recursive call.

Become a Member to join the conversation.