Login

Back

Recursion, iteration and divide and conquer

Introduction
Imagine a problem where you had to add a list of numbers, such as 1 + 3 + 5 + 7 + 9. How would you go about this? In programming, we might decide to use a loop, or we could use a technique known as 'divide and conquer' and use a recursive routine. We will investigate both approaches.

Iteration
If we wanted to add a list of numbers together, we might write a function that uses a for loop. We would then call that function and pass it a list of numbers we wanted to add together. Let's see how to do this in Python.

def myList(listOfNumbers):
    total = 0
    for i in listOfNumbers:
        total = total + i
   return total

print(mylist([1, 3, 5, 7, 9]))

There is nothing particularly 'wrong' with this solution because apart from anything else, it works. However, there is another way. In programming, there is a technique known as 'divide and conquer'. This means that we try and break down the problem into smaller problems, solve each of the smaller problems using recursion and then recombine the solutions to the smaller problems to get the answer to the original problem. 

Divide and conquer in practice
How could you divide up this problem? Let's break it down.

total = 1 + 3 + 5 + 7 + 9

This is a list. Add the first item in the list to a new list made up of all of the elements in the list except the first one, like this:

total = 1 + (3 + 5 + 7 + 9)

But (3 + 5 + 7 + 9) is a list. So as before, add the first item of this list to a new list made up of all of the elements in the list except the first one:

3 + (5 + 7 + 9)

But (5 + 7 + 9) is a list. So as before, add the first item of this list to a new list made up of all of the elements in the list except the first one:

5 + (7 + 9)

But (7 + 9) is a list. So as before, add the first item of this list to a new list made up of all of the elements in the list except the first one:

7 + (9)

But (9) is a list with only one element in it. This is the stopping condition for recursion.

9 is a list but it only has one element. A list with only one element is a special case. Every recursion problem has a special case and we always need to identify what it is as it is the condition that will be used to stop the recursion process. We will see this working in a moment when we write the algorithm.

What we have done is to break this problem down so that all we ever do (apart from in the special case) is to add two numbers together! In other words:

9 is a list with just one element in, our special case. We can't divide and conquer the problem any more.
We do 7 + 9 = 16. We pass 16 back.

Now we do 5 + 16 = 21. We pass 21 back.
Now we do 3 + 21 = 24. We pass 24 back.
Now we do 1 + 24 = 25. This is our answer.

We have broken the problem down into smaller parts. We can now solve the problem using recursion. Here is a recursive routine that will do the job:

def myList(listOfNumbers):
    if len(listOfNumbers) == 1:
        return listOfNumbers[0]
    else:
        return listOfNumbers[0] + myList(listOfNumbers[1:])

print(myList([1, 3, 5, 7, 9]))

Remember that the first element in any list is always counted from zero not one, which is why we use listOfNumbers[0]. Also note that [1:] takes a list and gets all of the elements from position 1 (i.e. the second element) to the end of the list, a process called 'splicing' a list. 

Notice the if statement checks to see if there is just one element in the list. If there is, it returns it and finishes as that is the answer. As we have already said, it is important to have a line like this in a recursive function because this is the line that will allow you to exit the recursive function. If you didn't have this line, you would constantly call the function you are in and eventually, you would run out of memory and the program would stop with a 'stack overfow' error.

Why is this function 'recursive'?
This is recursive function because it calls itself. If you look on the fifth line, return listOfNumbers[0] + myList(listOfNumbers[1:]) this says, get the first element in the list and add it to all of the other elements in the list, apart from the first one. The last part of this line is another call to the function you are currently in. This is another call to add a list! Sometimes, it is a lot easier to see what is happening in a recursive function by drawing a diagram:

recurse

Recursion takes most people some time to get their brains around so don't worry if you don't understand it first time. Keep working at it and practising different problems and eventually, it will click!

Back