Mission 3 - Recursion

Introduction

Recursion can be a challenging concept to understand, but bear with us, we will try to make it as simple as possible. A common definition of recursion is that it is the process in which a function calls itself directly or indirectly. So essentially,  a function calling itself.

 

A common question that is asked during technical interviews is “How would you explain recursion to a 5 year old?”. The idea is if you can explain something so complicated to  someone so young, you must have a good understanding.

 

To explain it to a 5 year old, one might use the following analogy. Say you have n number of students standing in a line. You are in the line as well and want to know your position on the line. What do you do? You ask the person in front of you, and they ask the person in front of them, and so on until they have reached the leader of the line. That person is the first person in line, so they turn around and tell the person behind them. Then the person behind will know that they are the second person in line, and turn around and tell the person behind them and so on. Once it gets back to you, you will know what position you are in line. That is a real life example of recursion.

 

To recap, for a function to be recursive, it must call itself and have a terminating condition. What is the point of the terminating condition? So that the function doesn’t call itself infinitely.

 

Let’s take a look at an example:

We want to write code that will add all of the numbers in a list. Before we knew recursion, we might do it like the following:

 

def sum(list):

    sum = 0

    #add every number in the list

    for i in range(0, len(list)):

        sum = sum + list[i]

    #Return the sum

    return sum

print(sum([5, 7, 3, 8, 10])

 

In the function above, we simply call the sum function and it returns the sum value of the list. In the last line we actually print the sum for the list [5, 7, 3, 8, 10] which is 33.

 

Now that we have learned recursion, we can rewrite the function above recursively:

 

def sum(list):

    if len(list) == 1:

        return list[0]

    else:

        return list[0] + sum(list[1:])

print(sum([5,7,3,8,10]))

 

Now let’s break down the recursive function above. If the length of the list is 1, it returns the list. This is known as the terminating condition. If the length is not 1, it returns the element and a call function() sum minus one element of the list. It will continue to do this until it reaches the terminating condition.