Question

So a friend of mine suggested I look into the Tower of Hanoi problem as a good example of using recursion. I'm not sure if the tower of hanoi is discussed later in the course (I'm only on lecture 5 or 6 now), but it is a very good example of how useful recursion can be. I implemented it in Python and I would recommend researching it online. http://codepad.org/zRnWuY2r Try solving a 12 stack and you'll see how powerful this short code is!

Answer 1

http://en.wikipedia.org/wiki/Tower_of_Hanoi
http://www.mazeworks.com/hanoi/
http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html

I thought I would post some of the sources I used in trying to understand this problem (took me a good while to wrap my head around it to be honest)

Answer 2

wow- using your code if you solve it for a stack of 12, there are 4096 moves!
Yes, the professor does a Tower of Hanoi demonstration in lecture 8. Thanks for the additional information, I found it helpful.

Answer 3

yep, the way you calculate it is (2^n)-1 so for 12 disks, (2^12)-1=4095 technically. The legend goes that there is a temple in hanoi where monks move 64 gold disks from one rod to the other following the rules laid out and when the entire stack is transferred the world will end. Which isn't anything to worry about because (2^64)-1 equals 18,446,744,073,709,551,616 moves, and at one a second would take around 584 billion years to complete lol It's a very interesting problem imo

Answer 4

oops...18,446,744,073,709,551,615 moves...not that that makes any real difference lol