Recursion

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 to sum 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 to sum, and so on until the Python interpreter detects too many recursive calls and shuts the program down.
• 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.