Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic trial
to watch this video
The next two sorting algorithms we look at will rely on recursion, which is the ability of a function to call itself. So before we move on, we need to show you how recursion works.
The next two sorting algorithms we look at will rely on recursion, which is the ability of a function to call itself. So before we move on, we need to show you how recursion works.
Let's suppose we needed to write a function that adds together all the numbers in an array (or, in the case of Python, a list). Normally, we'd probably use a loop for this sort of operation.
# The function takes a list of the numbers we want to add.
def sum(numbers):
# The total starts at zero.
total = 0
# We loop over every number contained in the list.
for number in numbers:
# And we add the current number to the total.
total += number
# Once we're done looping, we return the accumulated total.
return total
# If we call the sum function with a list of numbers, it will return the total.
# When we run this program it will print out that returned value, "19".
print(sum([1, 2, 7, 9]))
To demonstrate how recursion works, let's revise the sum
function to use recursion instead. Note that recursion is not the most efficient way to add a list of numbers together. But this is a good problem to use to demonstrate recursion, because it's so simple.
 One thing before we show you the recursive version, though. This example is going to use the Python slice syntax, so I need to take a moment to explain that for those not familiar with it.
 A slice is a way to get a series of values from a list.
 Let's load up the Python REPL, or Read Evaluate Print Loop, so I can demonstrate. Type this command in your terminal:
python
 The prompt will change to show we're in the Python REPL, not the shell.
 We'll start by creating a list of numbers to work with. Enter this statement:
numbers = [0, 1, 2, 3, 4]
 Like arrays in most other languages, Python list indexes start at 0. So
numbers[1]
will actually get the second item from the list.
numbers[1]
1
 With slice notation, I can actually get several items back. I type a colon, followed by the list index I want up to (but not including). So
numbers[1:4]
would get us the second up to (but not including) the fifth items from the list, that is, it will get us the second through the fourth items.
numbers[1:4]
[1, 2, 3]
 I know what you're thinking, and you're right. That "up to but not including" rule is a little counterintuitive.
 But you can just forget all about it for now, because we won't be using a second index with any of our Python slice operations in this course.
 Here's what we will be using: When you leave the second index off of a Python slice, it gives you the items from the first index up through the end of the list, wherever that is.
 So
numbers[1:]
will give us items from the second index up through the end of the list.
numbers[1:]
[1, 2, 3, 4]

numbers[2:]
will give us items from the third index up through the end of the list.
numbers[2:]
[2, 3, 4]
 You can also leave the first index off to get everything from the beginning of the list.
numbers[:3]
will get us everything from the beginning of the list up to (but not including) the third index.
numbers[:3]
[0, 1, 2]
 It's also worth noting that if you take a list with only one item, and you try to get everything from the (nonexistent) second item onwards, the result will be an empty list.
one_item = [0]
one_item[1:]
[]
 Don't worry too much about remembering Python slice syntax. It's not an essential part of sorting algorithms or recursion. I'm only explaining it to help you read the code you're about to see.
 Now that we've covered it, we can convert our
sum
function to a recursive function.
# It will take the list of numbers to add, just like before.
def sum(numbers):
# Now here's the recursive part. We'll have the "sum" function call itself.
# We use slice notation to pass the entire list of numbers EXCEPT the
# first one.
remaining_sum = sum(numbers[1:])
# Then we add the first number in the list to the result of the recursive
# function call, and return the result.
return numbers[0] + remaining_sum
print(sum([1, 2, 7, 9]))
 So if we call
sum
with four numbers first, it will call itself with the remaining three numbers. That call tosum
will then call itself with the remaining two numbers. And so on.  But if we try to run this, we'll get an error: "RecursionError: maximum recursion depth exceeded".
 This happens because
sum
gets into an infinite loop. It keeps calling itself, over and over.  The reason is that when we get down to a list of just one element, and we take a slice from the nonexistent second element to the end, the result is an empty list.
 That empty list gets passed to the recursive call to
sum
, which passes an empty list in its recursive call tosum
, and so on until the Python interpreter detects too many recursive calls and shuts the program down.
 That empty list gets passed to the recursive call to
 What we need is to add a base case to this recursive function; a condition where the recursion stops. This will keep it from getting into an infinite loop.
 With the sum function, the base case is when there are no elements left in the list. In that case, there is nothing left to add, and the recursion can stop.
 A base case is the alternative to a recursive case, a condition where recursion should occur. For the
sum
function, the recursive case is when there are still elements in the list to add together.  Let's add a base case at the top of the function.
def sum(numbers):
# Python treats a list that contains one or more values as a "true" value,
# and it treats a list containing _no_ values as a "false" value.
# So we'll add an "if" statement that says if there are no numbers in
# the list, we should return a sum of 0. That way, the function will exit
# immediately, without making any further recursive calls to itself.
if not numbers:
return 0
# We leave the code for the recursive case unchanged. If there are still
# numbers in the list, the function will call itself with any numbers
# after the first, then add the return value to the first number in the
# list.
remaining_sum = sum(numbers[1:])
return numbers[0] + remaining_sum
print(sum([1, 2, 7, 9]))
 Let's try running it. [
python recursion.py
] It will output the sum of the numbers in the list:19
.  If we added
print
statements to help us debug the code, the series of recursive calls would look like this:
$ python recursion.py
Calling sum([2, 7, 9])
Calling sum([7, 9])
Calling sum([9])
Calling sum([])
Call to sum([9]) returning 9 + 0
Call to sum([7, 9]) returning 7 + 9
Call to sum([2, 7, 9]) returning 2 + 16
Call to sum([1, 2, 7, 9]) returning 1 + 18
19
And there you have it, a simple recursive function. Well, the function is simple, but as you can see, the flow of control is very complex. Don't worry if you didn't understand every detail here, because we won't be using this particular example again. The fundamental mechanism you should remember is that a recursive function needs a recursive case that causes it to call itself, and it needs to eventually reach a base case that causes the recursion to stop.
The next two sorting algorithms we look at will rely on recursion, 0:00 which is the ability of a function to call itself. 0:04 So, before we move on, we need to show you how recursion works. 0:07 Recursive functions can be very tricky to understand. 0:11 Imagine a row of dominoes stood on end, 0:14 where one domino falling over causes the next domino to fall over, 0:17 which causes the next domino to fall over causing a chain reaction. 0:20 It's kind of like that. 0:24 Let's suppose we need to write a function that adds together all the numbers in 0:26 an array, or in the case of python, a list. 0:30 Normally we'd probably use a loop for this sort of operation. 0:32 The function takes a list of the numbers we want to add. 0:37 The total starts at zero. 0:40 We loop over every number contained in the list and 0:42 we add the current number to the total. 0:45 Once we're done looping we return the accumulated total. 0:48 If we call this sum function with a list of numbers, it'll return the total. 0:53 When we run this program, it'll print out that return value, 19. 0:57 Let's try it real quick, python recursion.py. 1:01 Whoops, mustn't forget to save my work here. 1:06 And run it and we see the result, 19. 1:10 To demonstrate how recursion works, 1:14 let's revise the sum function to use recursion instead. 1:16 Note that recursion is not the most efficient way to add a list of 1:20 numbers together. 1:23 But this is a good problem to use to demonstrate recursion because it's 1:25 so simple. 1:28 One thing before I show you the recursive version though. 1:29 This example is going to use the Python slice syntax. 1:32 So I need to take a moment to explain that for those not familiar with it. 1:35 A slice is a way to get a series of values from a list. 1:39 Let's load up the Python ripple or redevaluate print loop so 1:43 I can demonstrate. 1:47 We'll start by creating a list of numbers to work with. 1:49 Numbers equals a list with zero, one, 1:51 two, three, and four, containing those numbers. 1:56 Like a raise in most other languages, Python lists indexes start at zero. 2:00 So numbers one will actually get the second item from the list. 2:04 With slice notation, I can actually get several items back. 2:10 It looks like just accessing an individual index of a list, but 2:14 then I type a colon followed by the list index that I want up to but not including. 2:19 So numbers one colon four will get us a second up to but 2:25 not including the fifth item from the list. 2:29 That is, it'll get us the second through the fourth items. 2:32 Now I know what you're thinking and you're right. 2:36 That up to but not including rule is a little counter intuitive. 2:38 But you can just forget all about it for now because we won't be using a second 2:42 index with any of our Python slice operations in this course. 2:45 Here's what we will be using. 2:50 When you leave the second index off of a Python slice, it gives you the items 2:52 from the first index up through the end of the list, wherever that is. 2:56 So numbers one colon with no index following it will give us 2:59 items from the second index, up through the end of the list. 3:03 Numbers two colon will give us items from the third index up through the end of 3:07 the list. 3:11 You can also leave the first index off to get everything from the beginning of 3:12 the list. 3:16 Numbers colon three will get us everything from the beginning of the list up to but 3:17 not including the third index. 3:23 It's also worth noting that if you take a list with only item, and 3:25 you try to get everything from the nonexistent second item onwards, 3:28 the result will be an empty list. 3:32 So if I create a list with just one item in it. 3:36 And I try to access from the second element onwards. 3:40 The second element doesn't exist so the result will be an empty list. 3:45 Don't worry too much about remembering Python slice syntax. 3:51 It's not an essential part of sorting algorithms or recursion. 3:54 I'm only explaining it to help you read the code you're about to see. 3:58 So I'm gonna exit the Python Rebel. 4:02 Now that we've covered recursion, 4:04 we can convert our sum function to a recursive function. 4:06 It'll take the list of numbers to add, just like before. 4:09 Now, here's the recursive part. 4:13 We'll have the sum function call itself. 4:14 We use slice notation to pass the entire list of numbers except the first one, 4:17 then we add the first number in the list to the result of the recursive 4:22 function call and return the result. 4:26 So if we call sum with four numbers first, 4:29 it'll call itself with the remaining three numbers. 4:32 That call to sum will then call itself with the remaining two numbers and so on. 4:35 But if we save this and try to run it, python recursion.py. 4:41 Well first we get a syntax error. 4:49 It looks like I accidentally indented something I shouldn't have. 4:50 So let me go fix that real quick. 4:53 There we go. That suggested to Python that there was 4:58 a loop or something there when there wasn't. 5:00 So let's go back to the terminal and try running this again. 5:03 There we go. 5:06 Now we're getting the error I was expecting. 5:07 Recursion error. 5:09 Maximum recursion depth exceeded. 5:10 This happens because sum gets into an infinite loop. 5:13 It keeps calling itself over and over. 5:16 The reason is that when we get down to a list of just one element and 5:18 we take a slice from the nonexistent second element to the end, 5:22 the result is an empty list. 5:25 That empty list gets passed to the recursive call to sum, 5:28 which passes an empty list in its recursive call to sum. 5:31 And so on, until the Python interpreter detects too many recursive calls and 5:34 shuts the program down. 5:38 What we need is to add a base case to this recursive function. 5:39 A condition where the recursion stops, 5:43 this will keep it from getting into an infinite loop. 5:45 With the sum function, base case is when there are no elements left in the list. 5:48 In that case, there is nothing left to add and the recursion can stop. 5:52 A base case is the alternative to a recursive case, 5:56 a condition where recursion should occur for the sum function. 5:59 The recursive case is when there are still elements in the list to add together. 6:04 Let's add a base case at the top of the function. 6:08 Python treats a list that contains one or more values as a true value and 6:13 it treats a list containing no values as a false value. 6:17 So we'll add an if statement that says if there are no numbers in the list, 6:21 we should return a sum of zero. 6:25 That way, the function will exit immediately without making any further 6:27 recursive calls to itself. 6:31 We'll leave the code for the recursive case unchanged. 6:32 If there are still numbers in the list, 6:35 the function will call itself with any numbers after the first. 6:37 Then add the return value to the first number in the list. 6:41 Let's save this, and try running it again. 6:44 Python recursion.py. 6:47 It'll output the sum of the numbers in the list, 19, 6:51 but it's still not really clear how this worked. 6:54 Let's add a couple of print statements that will show us what it's doing. 6:57 We'll show the recursive call to sum and what it's being called with. 7:01 We'll also add a call to print right before we return, 7:08 showing which of the calls the sum is returning, and what it's returning. 7:11 Let me save this, and resize the console a bit. 7:20 And let's try running it again. 7:25 Python recursion.py. 7:28 Since the print calls are inside the sum function, the first call to sum([1, 2, 7, 7:31 9]) isn't shown, only the recursive calls are. 7:35 This first call to sum ignores the first item in the list, 1, 7:39 and calls itself recursively. 7:42 It passes the remaining items from the list, 2, 7 and 9. 7:44 That call to sum again ignores the first item in the list it receives, 2, and 7:48 again calls itself recursively. 7:52 It passes the remaining items in the list, 7 and 9. 7:55 That call ignores the 7, and calls itself with the 9. 7:58 And the last call shown here ignores the 9, and calls itself with an empty list. 8:01 At this point, none of our recursive calls to sum have returned yet. 8:08 Each of them is waiting on the recursive call it made to sum to complete. 8:11 Python and other programming languages use something called a call stack to keep 8:16 track of this series of function calls. 8:20 Each function call is added to the stack, 8:22 along with the place in the code that it needs to return when it completes. 8:25 But now the empty list triggers the base case causing the recursion to end and 8:28 the sum function to return zero. 8:33 That zero value is returned to its caller. 8:35 The caller adds the zero to the first and only value in its list, 9. 8:38 The result is 9. 8:43 That 9 value gets returned to the caller which adds it to the first value in 8:44 the list it received, 7. 8:49 The result is 16. 8:50 That 16 value is returned to the caller which adds it to the first value in 8:53 the list it received, 2. 8:58 The result is 18. 8:59 That 18 value is returned to the caller 9:02 which adds it to the first value in the list, 1. 9:05 The result is 19. 9:09 That 19 value is returned to the caller which is not the sum function recursively 9:11 calling itself, but our main program. 9:15 This is our final result which gets printed. 9:18 It's the same result we got from the loop base version of our program. 9:21 The end. 9:25 We don't want the print statements in our final version of the program, so 9:26 let me just delete those real quick. 9:30 And there you have it, a very simple recursive function. 9:31 Well, the function is simple. 9:35 But as you can see, the flow of control is very complex. 9:36 Don't worry if you didn't understand every detail here, 9:39 because we won't be using this particular example again. 9:43 There are two fundamental mechanisms you need to remember. 9:46 A recursive function means a recursive case that causes it to call itself. 9:49 And it also need to eventually reach a base case that causes 9:54 the recursion to stop. 9:58
You need to sign up for Treehouse in order to download course files.
Sign up