2018-03-27 Hanoi2 (2 days)

posted Mar 27, 2018, 6:06 AM by Konstantinovich Samuel   [ updated Mar 28, 2018, 5:46 AM ]
Tree Lab: Will check in class on the 28th
Open your tree lab to demo as I walk around. Show me that your sliders work for your tree-3 when I come by.

Goal: Towers of Hanoi 2: To understand recursion you must first... understand recursion.

define a function: 
def hanoi(n, start, temp, end):

n : the number of disks.
start temp and end : strings with the names of the towers.
The function must print the set of moves as seen in the examples below

hanoi(2, "A","B","C")
move from A to B
move from A to C
move from B to C

hanoi(3, "X","temp","Y")
move from X to Y
move from X to temp
move from Y to temp
move from X to Y
move from temp to X
move from temp to Y
move from X to Y

Think of this recursively, and remember that a base case that is "do nothing" just means you can write something like this with no else:

if you_have_more_to_do : 
   do recursion step(s)
   do recursion step(s)

The number of moves to solve a towers of hanoi with n disks is easily calculated.
Explicit definition:
tn = 2n - 1 
Recursive definition:
tn = 2 * t(n-1) + 1  [twice the previous result plus one]

Since this number is huge, computers cannot realistically compute results for any large values of n.

Remember Moore's Law:

Moore's law refers to an observation made by Intel co-founder Gordon Moore in 1965. He noticed that the number of transistors per square inch on integrated circuits had doubled every year since their invention. Moore's law predicts that this trend will continue into the foreseeable future

"I've heard the death of Moore's law more times than anything else in my career, and I'm here today to really show you and tell you that Moore's Law is alive and well and flourishing." Intel CEO Brian Krzanich (2017)

Moore's law does seem to predict speed increases as we can see from this chart of calculations per second per $1000: