• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

View

# Module 6 - Recursion

last edited by 4 years, 6 months ago

# Module 6 - Recursion

## Introduction

Recursion is simply put the ability of a function to recursively call itself. Recursion is quite easy and also quite practical. Just don't forget to put in an exit clause to your recursive functions or you will find yourself staring at a spinning hourglass while the algorithm chews up all your available resources.

## Tower of Hanoi

The classic example of a recursive solution to a relatively complex problem is the Tower of Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi - which is taught in every Computer Science program and in a lot of programming classes. As you add disks the solution becomes more complex, but it is a simple repetition of moves used in the 3 disk solution.

## Assignment

We are going to solve the classic Tower of Hanoi. Using the wikipedia article I want you to write a computer program that calculates the number of moves necessary to solve Tower of Hanoi given a number of disks. There are formulas that calculate this - you are NOT going to use them. You will calculate by going through the recursive algorithm of the tower and counting every time a block is moved.

1. What is the Complexity (In Big O)?

2. Should we be concerned with concerned with the legend of the world ending when the 64 disk solution is physically solved it it takes 2 seconds for each move?

## Quiz

By now you should be good at the quizzes - please complete the recursion quiz at http://geeksquiz.com/algorithms/recursion/

Assignment Grading Criteria - I don't need to actually see every move printed out (it may help you in coding the algorithm though) - I do need to see it actually counting the moves and it should give the correct number of moves for all cases which you can verify using the equation 2^n - 1.

Previous: Module 5 - Queues