Embedded Files
About
One of the most prominent algorithms programmers use in their daily lives is recursion. Many programmers consider it an elegant way to implement something that would normally take many nested loops. It can add clarity and help debug code as the loop is done all in one line. The Tower of Hanoi is a classic recursion problem that can be easily solved using recursion over iteration. This project is intended to show when recursion is useful and the time and space complexity of recursion versus iteration.
Words to know
Recursion: The act of defining a function that calls itself from within. Recursion is defined in two steps:
the base case and the recursive step.
Base case: An end case where recursion is not needed to produce an answer.
Recursive case: A set of rules that reduces all other cases to the base case.
Iteration: The act of repeating a set of instruction until a termination case is met. Iteration can be done via loops or iterators.
Loops
Loops have been around since before programming was invented and have a wide variety of flavors and applications. In python, there are three general types of loops : the for loop, the while loop, and the do-while loop. If any of these are unfamiliar to you, I recommend doing a quick Google search before starting this project.
Loops are iterative, as they can repeat code multiple times and require a clear set of steps to walk
through within the loop. Iteration requires a specific terminating condition to be met to terminate (a for loop repeats n number of times)
(a while loop finds its Boolean condition to no longer be true).
Recursion
Recursion on the other hand, does not use loops at all; instead, recursion uses functions that call
themselves to loop several times. Instead of a terminating condition explicitly specified, a recursive function loops until it meets the base case—the case where there can no longer be repetition—to know when to stop.
# Use these lines if using Python 3
import tkinter as tk
from tkinter import *
# Uncomment these lines if using Python 2
# import Tkinter as tk
# from Tkinter import *
import numpy as np
class Application(tk.Frame):
def __init__(self, master=None):
super().__init__()
self._master = master
# Creating a list of colors to pull from [15 colors]
self._piece_colors = ['red', 'blue', 'green', 'yellow', 'pink', 'purple', 'orange', 'black', 'grey',
'deep sky blue', 'lawn green', 'saddle brown', 'gold', 'thistle', 'hot pink', 'brown4']
# Create frame
self.winfo_toplevel().title("Tower of Hanoi Simulation")
self._frame = Frame(self._master)
self._frame.pack(fill=BOTH, expand=TRUE)
self.pack(fill=BOTH, expand=TRUE)
# Creating canvas
self._canvas = Canvas(master=self._master, width=800, height=600)
self._width, self._height = 800, 600 # Hard coded dimensions of width and height for now
self._canvas.pack()
# Create box to enter piece number
self._piece_num = Entry(self._master, width=10)
# Creating pegs
self._pegs = []
self._peg_state = [[], [], []]
self._peg_width = 10
self._peg_dist = self._width // 3
self._peg_height = self._height // 2
# Creating pieces
self._num_pieces = 0
self._pieces = {}
self._piece_height = self._peg_height // 16
self._max_piece_width = self._peg_dist * 2 // 3
self._min_piece_width = 2 * self._peg_width
self._init_ui()
self._testing = True
self._testing_UI = False
def _init_ui(self):
# Generate UI pegs
self._generate_pegs()
# Generate piece entry
piece_label = StringVar()
piece_dir = Label(self._master, textvariable=piece_label, height=4)
piece_label.set("Enter number of disks: ")
piece_dir.pack(side=LEFT)
self._piece_num.pack(side=LEFT, padx=5, pady=5)
# Creating checkbox
self._iterative = IntVar()
iterative_check = Checkbutton(master=self._master, text="Iterative?", variable=self._iterative, onvalue=1,
offvalue=0)
iterative_check.pack(side=RIGHT, padx=5, pady=5)
# Creating buttons
gen_button = Button(master=self._master, text="Generate", command=self._if_generate)
gen_button.pack(side=RIGHT, padx=5, pady=5)
calc_button = Button(master=self._master, text="Calculate", command=self._if_calculate)
calc_button.pack(side=RIGHT, padx=5, pady=5)
def _generate_peg_dims(self):
x1, y1 = (self._peg_dist - self._peg_width) // 2, self._height * 1 // 3
x2, y2 = x1 + self._peg_width, y1 + self._peg_height
return x1, y1, x2, y2
def _generate_pegs(self):
# Generate first peg
x1, y1, x2, y2 = self._generate_peg_dims()
p = self._canvas.create_rectangle(x1, y1, x2, y2, fill='blanched almond')
self._pegs.append(p)
# Generate second and third peg
for i in range(2):
x1, x2 = x1 + self._peg_dist, x2 + self._peg_dist
p = self._canvas.create_rectangle(x1, y1, x2, y2, fill='blanched almond')
self._pegs.append(p)
self._master.update()
def _generate_pieces(self):
# remove pieces
for p in self._pieces.values():
self._canvas.delete(p)
for i in range(len(self._peg_state )):
self._peg_state[i] = []
x1, y1, x2, y2 = self._generate_peg_dims()
x1, y1 = (self._peg_dist - self._max_piece_width) // 2, y2 - self._piece_height - 2
x2, y2 = x1 + self._max_piece_width, y1 + self._piece_height
dx = (self._max_piece_width - self._min_piece_width) // (2 * max(1, self._num_pieces - 1))
for i in range(self._num_pieces - 1, -1, -1):
p = self._canvas.create_rectangle(x1, y1, x2, y2, fill=self._piece_colors[i])
self._pieces[i] = p
self._peg_state[0].append(i)
x1, x2 = x1 + dx, x2 - dx
y1, y2 = y1 - self._piece_height - 2, y2 - self._piece_height - 2
self._master.update()
self._master.after(25)
def _if_pause(self):
# self._master.after(10)=
self._output_state()
def _output_state(self): # troubleshooting function
print('objects')
for obj in self._canvas.find_all():
print(obj, ': ', self._canvas.bbox(obj))
print('peg states')
print(self._peg_state)
def _if_generate(self):
# Make sure pieces is an int
if self._piece_num.get():
self._num_pieces = int(self._piece_num.get())
# If the amount of pieces is not reasonable, set to 4
if self._num_pieces < 4 or self._num_pieces > 15:
self._num_pieces = 4
else:
# If the number of pieces is not specified, set to 4
self._num_pieces = 4
self._generate_pieces()
def hanoi_recursive(n, a, b, c):
pass
def hanoi_iterative(n, a, b, c):
pass
def _if_calculate(self):
# Move pieces from a to b
if self._iterative.get() == 1:
self.hanoi_iterative(self._num_pieces, 0, 1, 2)
else:
self.hanoi_recursive(self._num_pieces, 0, 1, 2)
self.hanoi_recursive(self._num_pieces, 1, 2, 0)
def move(self, i, a, b):
if(self._testing or self._testing_UI):
print('moving', i, a, b)
if self._peg_state[a][-1] != i:
raise RuntimeError('Peg not on top of pile (or not in pile)')
self._peg_state[a].remove(i)
p = self._pieces[i]
# Lift piece above peg A (moving up)
ax1, ay1, ax2, ay2 = self._canvas.bbox(self._pegs[a])
while True:
x1, y1, x2, y2 = self._canvas.bbox(p)
if y1 < ay1 - 50:
break
self._canvas.move(p, 0, -1)
self._master.update()
if self._testing_UI:
print(' lifted from peg A')
self._output_state()
# Move piece towards peg B (moving right/left)
bx1, by1, bx2, by2 = self._canvas.bbox(self._pegs[b])
new_center = (bx1 + bx2) // 2
while True:
x1, y1, x2, y2 = self._canvas.bbox(p)
center = (x1 + x2) // 2
if center == new_center:
break
if center > new_center:
self._canvas.move(p, -1, 0)
else:
self._canvas.move(p, 1, 0)
self._master.update()
if self._testing_UI:
print(' moved to peg A')
self._output_state()
# Move it down on top of the previous piece (moving down)
self._piece_height = y2 - y1
new_bottom = by2 - self._piece_height * len(self._peg_state[b])
while True:
x1, y1, x2, y2 = self._canvas.bbox(p)
if y2 >= new_bottom:
break
self._canvas.move(p, 0, 1)
self._master.update()
self._peg_state[b].append(i)
if self._testing_UI:
print(' moved down')
self._output_state()
print('---------')
if self._testing:
print('new peg state', self._peg_state)
print()
def top_disk(self,peg):
if(len(self._peg_state[peg])):
return self._peg_state[peg][-1] #Now they can't mess with it!
return np.inf
Page updated
Google Sites
Report abuse