Python Programming Project

Tower of Hanoi

1. Recursion

Let’s start with recursion. What is recursion? As its name suggests, recursion is when your program recurs. In computer science, this means that your function calls itself. We use recursion because it allows us to break down large problems or solutions into smaller, simpler versions of themselves. This will make more sense when you get to see some examples, so let’s jump right in.

1.1 Recursion in Maths

Recursion can help us compute some mathematical problems easily. Here, we’ll look at 2 examples: the Fibonacci sequence, and calculating factorials.

1.1.2 Fibonacci sequence

The Fibonacci sequence is a sequence of numbers which are defined by the following equation:

From this equation, we can tell that the Fibonacci sequence is in fact a recurrence relation and we can easily come up with the code to compute it.

def fib(n):

     if n < 2:

          return n

     return fib(n-1) + fib(n-2)

print (fib(30))

Note how in the example code above, the function we define fib(n) calls a smaller version of itself, fib(n-2) and fib(n-1). This is essentially the meaning of recursion. This code then prints fib(30), the 30^th number in the sequence, which is 832040.

Notice also how we are careful to state that F₁=1 and F₂=1 in the equation. This is reflected in the code in the if loop to return n should n <2. This is called the base case, and is crucial to recursion as it stops the program from calling on itself again. Every recursion must have at least one base case, and some have more.

1.1.3 Factorials

Another thing we can do using recursion is calculating factorials. Factorials are defined by the following recurrence relation:

We can then write a recursive algorithm for this code as such:

def factorial(n):

     if n == 1:

          return 1

     else:

          return n * factorial(n-1)

print (factorial(10))

Just like with the Fibonacci recursion, the function for factorial calls itself, factorial(n-1).

Now that we’ve discussed recursion in maths, why not try working on a few simple problems to see if you’ve really got the hang of simple recursion algorithms!

1.2 Computer Science (Additional reading)

Now let’s move on to recursion in computer science. The solution for the Tower of Hanoi game does not require use of sorting algorithms, but as programmers, sorting algorithms are very important to us and we need to know them anyway.

Sorting algorithms are algorithms which help us to order an unordered list, usually in numerical or lexicographical order. There are many different types of sorting algorithms which approach the problem in many different ways. The use of recursion in sorting can significantly cut down the time taken for a list to be sorted, which becomes increasingly important as the list increases in size.

We’ll look quickly at two different specific sorting algorithms: Insertion sort and Quicksort

1.2.1 Insertion Sort

Insertion sort is a type of simple sort, which simply takes elements from the unordered list and inserts it into its proper position in a new, sorted list. The algorithm for insertion sort is as follows:

def insertionSort(myList):

     for index in range(1,len(myList)):

          currentvalue = myList[index]

          position = index

          while position>0 and myList[position-1]>currentvalue:

               myList[position]=myList[position-1]

               position = position-1

          myList[position]=currentvalue

myList = [54,26,93,17,77,31,44,55,20]

insertionSort(alist)

print(alist)

The code above takes myList [54,26,93,17,77,31,44,55,20] and sorts it by insertion sort and returns [17, 20, 26, 31, 44, 54, 55, 77, 93]. On average, the time needed to sort an array of size n is time n². Since myList is relatively short, it happens quickly. But when there are longer lists, the time needed can increase. So, we use a more efficient algorithm: Quicksort

1.2.2 Quicksort

Quicksort is a type of divide and conquer algorithm, which is a type of recursive algorithm. The code for Quicksort is quite complex and we will not go into detail here, but the basics of how Quicksort works is that an element in the array is picked to be the pivot. The array is then reordered so that all elements with smaller values than the pivot are in front of it while the elements with larger values go after it. The pivot is then in its proper position. The above sequence is applied recursively to the sub-arrays created on each side of the pivot until all elements are sorted.

On average case scenarios, the Quicksort algorithm takes a time of around n log n for an array of size n. Compared to n² of the insertion sort algorithm, this makes a huge difference, especially when the array is large!

1.3 Other things to note

We’ve seen that recursion is great at helping us solve problems. But beware – it might provide an elegant solution, but that solution is not always necessarily the best. Recursive functions can make use of a lot of memory, and can end up causing stack overflow and make your program crash, so you need to watch out!

1.4 Summary

This lesson, we’ve discussed

• Recursion in maths
• Recursion in sorting algorithms

There are in fact many more uses of recursive algorithms in computer, not only in sorting but also in other areas, for example, in trees. Do read up on them if you are interested to find out more about recursion.

You might also want to look into iteration, which has similarities to recursion and is also a very useful tool to have!