CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion, Part 2

File System Navigation
Fractals
1. kochSnowflake
2. sierpinskiTriangle
Backtracking
1. maze solving
2. nQueens
Memoization

File System Navigation
Folders can contain folders or files. Since folders can contain other folders, they are a recursive data structure. In fact, they are a kind of recursive structure called a tree (where each value has exactly one parent, and there is a topmost or "root" value). Traversing such a recursive data structure is a natural use of a recursive algorithm!

These programs only run locally (not in the browser), and require that you first download and expand sampleFiles.zip in the same folder as the Python file you are running.
1. printFiles
  
  import os def printFiles(path): # Base Case: a file. Just print the path name. if os.path.isfile(path): print(path) else: # Recursive Case: a folder. Iterate through its files and folders. for filename in os.listdir(path): printFiles(path + '/' + filename) printFiles('sampleFiles') # Note: if you see .DS_Store files in the sampleFiles folders, or in the # output of your function (as often happens with Macs, in particular), # don't worry: this is just a metadata file and can be safely ignored.
2. listFiles
  
  import os def listFiles(path): if os.path.isfile(path): # Base Case: return a list of just this file return [ path ] else: # Recursive Case: create a list of all the recursive results from # all the folders and files in this folder files = [ ] for filename in os.listdir(path): files += listFiles(path + '/' + filename) return files print(listFiles('sampleFiles'))
3. removeTempFiles
  Note: Be careful when using os.remove(): it's permanent and cannot be undone!
  That said, this can be handy, say to remove .DS_Store files on Macs, and can be modified to remove other kinds of files, too. Just be careful.
  import os def removeTempFiles(path, suffix='.DS_Store'): if path.endswith(suffix): print(f'Removing file: {path}') os.remove(path) elif os.path.isdir(path): for filename in os.listdir(path): removeTempFiles(path + '/' + filename, suffix) removeTempFiles('sampleFiles') # removeTempFiles('sampleFiles', '.txt') # be careful

Fractals
A fractal is a recursive graphic (that is, a graphic that appears the same at different levels as you zoom into it, so it appears to be made of smaller versions of itself). In theory you can zoom forever into a fractal, but here we will keep things simple and draw fractals only up to a specified level. Our base case will be when we reach that level. We'll use the following framework for most fractals:

from cmu_112_graphics import * from tkinter import * class MyFractalApp(App): def appStarted(self): self.level = 1 def drawFractal(self, canvas, level, otherParams): if level == 0: pass # base case else: pass # recursive case; call drawFractal as needed with level-1 def keyPressed(self, event): if event.key in ['Up', 'Right']: self.level += 1 elif (event.key in ['Down', 'Left']) and (self.level > 0): self.level -= 1 def redrawAll(self, canvas): margin = min(self.width, self.height)//10 otherParams = None self.drawFractal(canvas, self.level, otherParams) canvas.create_text(self.width/2, 0, text = 'Level %d Fractal' % (self.level), font = 'Arial ' + str(int(margin/3)) + ' bold', anchor='n') canvas.create_text(self.width/2, margin, text = 'Use arrows to change level', font = 'Arial ' + str(int(margin/4)), anchor='s') canvas.create_text(self.width/2, self.height/2, text = 'Replace this with your fractal', font = 'Arial 24 bold') MyFractalApp(width=400, height=400)
1. sierpinskiTriangle
  
  from cmu_112_graphics import * from tkinter import * class SierpinskiTriangleApp(App): def appStarted(self): self.level = 1 def drawSierpinskiTriangle(self, canvas, level, x, y, size): # (x,y) is the lower-left corner of the triangle # size is the length of a side # Need a bit of trig to calculate the top point if level == 0: topY = y - (size**2 - (size/2)**2)**0.5 canvas.create_polygon(x, y, x+size, y, x+size/2, topY, fill='black') else: # Bottom-left triangle self.drawSierpinskiTriangle(canvas, level-1, x, y, size/2) # Bottom-right triangle self.drawSierpinskiTriangle(canvas, level-1, x+size/2, y, size/2) # Top triangle midY = y - ((size/2)**2 - (size/4)**2)**0.5 self.drawSierpinskiTriangle(canvas, level-1, x+size/4, midY, size/2) def keyPressed(self, event): if event.key in ['Up', 'Right']: self.level += 1 elif (event.key in ['Down', 'Left']) and (self.level > 0): self.level -= 1 def redrawAll(self, canvas): margin = min(self.width, self.height)//10 x, y = margin, self.height-margin size = min(self.width, self.height) - 2*margin self.drawSierpinskiTriangle(canvas, self.level, x, y, size) canvas.create_text(self.width/2, 0, text = 'Level %d Fractal' % (self.level), font = 'Arial ' + str(int(margin/3)) + ' bold', anchor='n') canvas.create_text(self.width/2, margin, text = 'Use arrows to change level', font = 'Arial ' + str(int(margin/4)), anchor='s') SierpinskiTriangleApp(width=400, height=400)
  
  Result:
  
  Side-by-Side Levels:
  from cmu_112_graphics import * from tkinter import * class SideBySideSierpinskiTrianglesApp(App): def appStarted(self): self.level = 0 def drawSierpinskiTriangle(self, canvas, level, x, y, size): # (x,y) is the lower-left corner of the triangle # size is the length of a side # Need a bit of trig to calculate the top point if level == 0: topY = y - (size**2 - (size/2)**2)**0.5 canvas.create_polygon(x, y, x+size, y, x+size/2, topY, fill='black') else: # Bottom-left triangle self.drawSierpinskiTriangle(canvas, level-1, x, y, size/2) # Bottom-right triangle self.drawSierpinskiTriangle(canvas, level-1, x+size/2, y, size/2) # Top triangle midY = y - ((size/2)**2 - (size/4)**2)**0.5 self.drawSierpinskiTriangle(canvas, level-1, x+size/4, midY, size/2) # Add circles around self.level (left side) to show how # level N is made up of 3 level N-1's: if (level == self.level): h = size * 3**0.5/2 cx, cy, r = x+size/2, y-h/3, size/3**0.5 canvas.create_oval(cx-r, cy-r, cx+r, cy+r, fill=None, outline='pink') def keyPressed(self, event): if event.key in ['Up', 'Right']: self.level += 1 elif (event.key in ['Down', 'Left']) and (self.level > 0): self.level -= 1 def drawLevel(self, canvas, level, cx): margin = min(self.width, self.height)//10 size = min(self.width, self.height) - 2*margin x, y = cx-size/2, self.height-margin self.drawSierpinskiTriangle(canvas, level, x, y, size) canvas.create_text(cx, 0, text = 'Level %d Fractal' % (level), font = 'Arial ' + str(int(margin/3)) + ' bold', anchor='n') canvas.create_text(cx, margin, text = 'Use arrows to change level', font = 'Arial ' + str(int(margin/4)), anchor='s') def redrawAll(self, canvas): self.drawLevel(canvas, self.level, self.width/4) self.drawLevel(canvas, self.level+1, self.width*3/4) # draw the right arrow between the levels canvas.create_text(self.width/2, self.height/2, text=u'\u2192', font='Arial 50 bold') SideBySideSierpinskiTrianglesApp(width=800, height=400)
2. kochSnowflake
  
  # This example uses turtle graphics, not Tkinter import turtle def drawKochSide(length, level): if (level == 1): turtle.forward(length) else: drawKochSide(length/3, level-1) turtle.left(60) drawKochSide(length/3, level-1) turtle.right(120) drawKochSide(length/3, level-1) turtle.left(60) drawKochSide(length/3, level-1) def drawKochSnowflake(length, level): for step in range(3): drawKochSide(length, level) turtle.right(120) def drawKochExamples(): turtle.delay(1) turtle.speed(0) turtle.penup() turtle.goto(-300,100) turtle.pendown() turtle.pencolor('black') drawKochSide(300, 4) turtle.pencolor('blue') drawKochSnowflake(300, 4) turtle.penup() turtle.goto(-250,50) turtle.pendown() turtle.pencolor('red') drawKochSnowflake(200, 5) turtle.done() drawKochExamples()
  
  Result:

Backtracking
1. maze solving
  Python code: maze-solver.py
  Key excerpt:
  def solve(row,col): # base cases if (row,col) in visited: return False visited.add((row,col)) if (row,col)==(targetRow,targetCol): return True # recursive case for drow,dcol in [NORTH,SOUTH,EAST,WEST]: if isValid(data, row,col,(drow,dcol)): if solve(row+drow,col+dcol): return True visited.remove((row,col)) return False
2. nQueens
  Python code: nQueens.py
  Key excerpt:
  def solve(col): if (col == n): return make2dSolution(queenRow) else: # try to place the queen in each row in turn in this col, # and then recursively solve the rest of the columns for row in range(n): if isLegal(row,col): queenRow[col] = row # place the queen and hope it works solution = solve(col+1) if (solution != None): # ta da! it did work return solution queenRow[col] = -1 # pick up the wrongly-placed queen # shoot, can't place the queen anywhere return None

Memoization
Memoization is a general technique to make certain recursive applications more efficient. The Big idea: when a program does a lot of repetitive computation, store results as they are computed, then look up and reuse results when available.
1. The problem:
  def fib(n): if (n < 2): return 1 else: return fib(n-1) + fib(n-2) import time def testFib(maxN=40): for n in range(maxN+1): start = time.time() fibOfN = fib(n) ms = 1000*(time.time() - start) print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms') testFib() # gets really slow!
2. A solution:
  fibResults = dict() def fib(n): if (n in fibResults): return fibResults[n] if (n < 2): result = 1 else: result = fib(n-1) + fib(n-2) fibResults[n] = result return result import time def testFib(maxN=40): for n in range(maxN+1): start = time.time() fibOfN = fib(n) ms = 1000*(time.time() - start) print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms') testFib() # ahhh, much better!
3. A more elegant solution:
  def memoized(f): # You are not responsible for how this decorator works. You can just use it! import functools cachedResults = dict() @functools.wraps(f) def wrapper(*args): if args not in cachedResults: cachedResults[args] = f(*args) return cachedResults[args] return wrapper @memoized def fib(n): if (n < 2): return 1 else: return fib(n-1) + fib(n-2) import time def testFib(maxN=40): for n in range(maxN+1): start = time.time() fibOfN = fib(n) ms = 1000*(time.time() - start) print(f'fib({n:2}) = {fibOfN:8}, time = {ms:5.2f}ms') testFib() # ahhh, much better!

CMU 15-112: Fundamentals of Programming and Computer Science Class Notes: Recursion, Part 2

CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion, Part 2