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

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

Module 6 - Recursion

Page history last edited by Dr. Ron Eaglin 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.

 

Answer the following questions in the interface of your code;

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

Next: Module 7 - Sorting Part 1

 

Comments (0)

You don't have permission to comment on this page.