CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion, Part 2
- 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.
- 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. - 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')) - 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
- printFiles
- 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)
- 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) - 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:
- sierpinskiTriangle
- Backtracking
- What is Backtracking?
Start with this introductory video on backtracking: - A Generic Backtracking Solver
############################################## # Generic backtracking-based puzzle solver # # Subclass this class to solve your puzzle # using backtracking. # # To see how useful backtracking is, run with checkConstraints=True # and again with checkConstraints=False # You will see the number of total states go up (probably by a lot). ############################################## import copy, time class BacktrackingPuzzleSolver(object): def solve(self, checkConstraints=True, printReport=False): self.moves = [ ] self.states = set() # If checkConstraints is False, then do not check the backtracking # constraints as we go (so instead do an exhaustive search) self.checkConstraints = checkConstraints # Be sure to set self.startArgs and self.startState in __init__ self.startTime = time.time() self.solutionState = self.solveFromState(self.startState) self.endTime = time.time() if (printReport): self.printReport() return (self.moves, self.solutionState) def printReport(self): print() print('***********************************') argsStr = str(self.startArgs).replace(',)',')') # remove singleton comma print(f'Report for {self.__class__.__name__}{argsStr}') print('checkConstraints:', self.checkConstraints) print('Moves:', self.moves) print('Solution state: ', end='') if ('\n' in str(self.solutionState)): print() print(self.solutionState) print('------------') print('Total states:', len(self.states)) print('Total moves: ', len(self.moves)) millis = int((self.endTime - self.startTime)*1000) print('Total time: ', millis, 'ms') print('***********************************') def solveFromState(self, state): if state in self.states: # we have already seen this state, so skip it return None self.states.add(state) if self.isSolutionState(state): # we found a solution, so return it! return state else: for move in self.getLegalMoves(state): # 1. Apply the move childState = self.doMove(state, move) # 2. Verify the move satisfies the backtracking constraints # (only proceed if so) if ((self.stateSatisfiesConstraints(childState)) or (not self.checkConstraints)): # 3. Add the move to our solution path (self.moves) self.moves.append(move) # 4. Try to recursively solve from this new state result = self.solveFromState(childState) # 5. If we solved it, then return the solution! if result != None: return result # 6. Else we did not solve it, so backtrack and # remove the move from the solution path (self.moves) self.moves.pop() return None # You have to implement these: def __init__(self): # Be sure to set self.startArgs and self.startState here pass def stateSatisfiesConstraints(self, state): # return True if the state satisfies the solution constraints so far raise NotImplementedError def isSolutionState(self, state): # return True if the state is a solution raise NotImplementedError def getLegalMoves(self, state): # return a list of the legal moves from this state (but not # taking the solution constraints into account) raise NotImplementedError def doMove(self, state, move): # return a new state that results from applying the given # move to the given state raise NotImplementedError ############################################## # Generic State Class # # Subclass this with the state required by your problem. # Note that this is a bit hacky with __eq__, __hash__, and __repr__ # (it's fine for 112, but after 112, you should take the time to # write better class-specific versions of these) ############################################## class State(object): def __eq__(self, other): return (other != None) and self.__dict__ == other.__dict__ def __hash__(self): return hash(str(self.__dict__)) # hack but works even with lists def __repr__(self): return str(self.__dict__) - Subset Sum
watch both: part1
and part2
The subsetSum problem takes a list of positive values (we'll use integers), and a target sum, and returns a sublist of values in the original list that sum to that target, or None if no such sum exists.############################################## # SubsetSumSolver and SubsetSumState ############################################## class SubsetSumState(State): def __init__(self, remainingValues, partialSolution): # remainingValues: the values still left in L to consider using # partialSolution: the values we have already added to our solution self.remainingValues = remainingValues self.partialSolution = partialSolution def __repr__(self): return str(self.partialSolution) class SubsetSumSolver(BacktrackingPuzzleSolver): def __init__(self, L, target): assert(min(L) > 0) # assume all the values in L are positive self.L = L self.target = target self.startArgs = (L, target) # for printReport self.startState = SubsetSumState(L, [ ]) def stateSatisfiesConstraints(self, state): return sum(state.partialSolution) <= self.target def isSolutionState(self, state): return sum(state.partialSolution) == self.target def getLegalMoves(self, state): if (state.remainingValues == [ ]): # No values remain, so there are no moves! return [ ] else: # There are two possible moves -- use the next value or skip it return ['use', 'skip'] # this is very clear if a bit pedantic def doMove(self, state, move): first = state.remainingValues[0] rest = state.remainingValues[1:] if (move == 'use'): newState = SubsetSumState(rest, state.partialSolution + [first]) else: # move == 'skip' newState = SubsetSumState(rest, state.partialSolution) return newState SubsetSumSolver([3, 6, 5, 2, 11, 7, 3], 15).solve(printReport=True) SubsetSumSolver([3, 6, 5, 2, 11, 7, 3], 15).solve(checkConstraints=False, printReport=True) # Here is a variable-sized example. As you make N larger, # backtracking becomes increasingly helpful: N = 50 L = list(range(1, N+1)) target = sum(L[0:N:2]) SubsetSumSolver(L, target).solve(printReport=True) SubsetSumSolver(L, target).solve(checkConstraints=False, printReport=True) - nQueens
The nQueens problem takes a positive integer N and returns an NxN chess board containing N queens placed so that no two queens attack each other, or None if no such board exists. Two queens attack each other if they are in the same row, the same column, or on the same diagonal (either diagonal -- up-to-the-right or down-to-the-right).############################################## # NQueensSolver and NQueensState ############################################## class NQueensState(State): def __init__(self, n, queenPositions): self.n = n # queenPositions is a list of (row, col) positions of each queen self.queenPositions = queenPositions def __repr__(self): board = [ (['-'] * self.n) for row in range(self.n) ] for (row, col) in self.queenPositions: board[row][col] = 'Q' return '\n'.join([' '.join(row) for row in board]) class NQueensSolver(BacktrackingPuzzleSolver): def __init__(self, n): self.n = n self.startArgs = (n,) # for printReport self.startState = NQueensState(n, [ ]) @staticmethod def queensAttackEachOther(row1, col1, row2, col2): return ((row1 == row2) # same row or (col1 == col2) # same col or (row1+col1 == row2+col2) # same up-to-the-right diagonal or (row1-col1 == row2-col2)) # same down-to-the-right diagonal def stateSatisfiesConstraints(self, state): # The constraints are satisifed if no two queens can attack each other, # But we check this as we go, so we only have to check the last queen! (row1, col1) = state.queenPositions[-1] # this is the last queen added for (row2, col2) in state.queenPositions[:-1]: if (self.queensAttackEachOther(row1, col1, row2, col2)): return False return True def isSolutionState(self, state): if (len(state.queenPositions) < self.n): return False # Confirm that no two queens attack each other, but we have to check all # pairs of queens (since we can call solver with checkConstraints=False) for i in range(self.n): (row1, col1) = state.queenPositions[i] for j in range(i): (row2, col2) = state.queenPositions[j] if (self.queensAttackEachOther(row1, col1, row2, col2)): return False return True def getLegalMoves(self, state): col = len(state.queenPositions) if (col == self.n): return [ ] else: return [(row, col) for row in range(self.n)] def doMove(self, state, move): newQueenPositions = state.queenPositions + [move] return NQueensState(self.n, newQueenPositions) NQueensSolver(7).solve(printReport=True) NQueensSolver(7).solve(checkConstraints=False, printReport=True) - Maze Solving
Note: this example does not use the generic backtracking solver from above, and it also does not use the cmu_112_graphics animation framework. You are not responsible for reproducing all the code for this example, but you should understand at a high level how it is using backtracking to solve a maze. In particular, run the code, press 'b' to enter backtracking mode, then press the right arrow repeatedly to watch how backtracking solves the maze step-by-step.
Python code: notes-recursion-maze-solver.py
Key excerpt:NORTH = (-1, 0) SOUTH = ( 1, 0) EAST = ( 0, 1) WEST = ( 0, -1) def isValid(data, row, col, direction): if not (0 <= row < len(data.maze) and 0 <= col < len(data.maze[0])): return False return direction in data.maze[row][col].bridges def solve(data, row, col, visited, alreadySeen): if row == len(data.maze)-1 and col == len(data.maze[0])-1: return visited for direction in [SOUTH, EAST, NORTH, WEST]: drow, dcol = direction if isValid(data, row, col, direction) and \ (row + drow, col + dcol) not in alreadySeen: visited.append((row + drow, col + dcol)) alreadySeen.add((row + drow, col + dcol)) tmpSolution = solve(data, row + drow, col + dcol, visited, alreadySeen) if tmpSolution != None: return tmpSolution visited.pop() # We won't undo alreadySeen, because we know we can't reach the end from there. return None def solveMaze(data): visited = [(0, 0)] alreadySeen = set() return solve(data, 0, 0, visited, alreadySeen)
- What is Backtracking?
- 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.
- 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!
- 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!
- 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!
- The problem: