CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion (Continued)

Using Multiple Recursive Calls
1. fibonacci
2. towersOfHanoi
3. floodFill
Using Recursive Results
1. powerset
2. permutations
Applications of Recursion
Backtracking
1. maze solving
2. nQueens
Improving Efficiency with Memoization
Expanding the Stack Size and Recursion Limit

Using Multiple Recursive Calls
1. fibonacci
  1. First attempt
    # Note: as written, this function is very inefficient! # (We need to use "memoization" to speed it up! See below for details!) def fib(n): if (n < 2): # Base case: fib(0) and fib(1) are both 1 return 1 else: # Recursive case: fib(n) = fib(n-1) + fib(n-2) return fib(n-1) + fib(n-2) print([fib(n) for n in range(15)])
  2. Once again, printing call stack using recursion depth:
    def fib(n, depth=0): print(" "*depth, "fib(", n, " )") if (n < 2): # Base case: fib(0) and fib(1) are both 1 return 1 else: return fib(n-1, depth+1) + fib(n-2, depth+1) fib(4)
  3. Even better (printing result, too):
    def fib(n, depth=0): print(" "*depth, "fib(", n, " )") if (n < 2): result = 1 # Base case: fib(0) and fib(1) are both 1 print(" "*depth, "-->", result) return result else: result = fib(n-1, depth+1) + fib(n-2, depth+1) print(" "*depth, "-->", result) return result fib(4)
  4. Finally, not duplicating code:
    def fib(n, depth=0): print(" "*depth, "fib(", n, " )") if (n < 2): result = 1 else: result = fib(n-1, depth+1) + fib(n-2, depth+1) print(" "*depth, "-->", result) return result fib(4)
2. towersOfHanoi
  1. First attempt (without Python):
    # This is the plan to solve Towers of Hanoi (based on magic!) magically move(n-1, source, temp, target) move( 1, source, target, temp) magically move(n-1, temp, target, source)
  2. Turn into Python (The "magic" is recursion!):
    def move(n, source, target, temp): move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) move(2, 0, 1, 2) # Does not work -- infinite recursion
  3. Once again, with a base case:
    def move(n, source, target, temp): if (n == 1): print((source, target), end="") else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) move(2, 0, 1, 2)
  4. Once more, with a nice wrapper:
    def move(n, source, target, temp): if (n == 1): print((source, target), end="") else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) def hanoi(n): print("Solving Towers of Hanoi with n =", n) move(n, 0, 1, 2) print() hanoi(4)
  5. And again, printing call stack and recursion depth:
    def move(n, source, target, temp, depth=0): print((" " * 3 * depth), "move", n, "from", source, "to", target, "via", temp) if (n == 1): print((" " * 3 * depth), (source, target)) else: move(n-1, source, temp, target, depth+1) move( 1, source, target, temp, depth+1) move(n-1, temp, target, source, depth+1) def hanoi(n): print("Solving Towers of Hanoi with n =", n) move(n, 0, 1, 2) print() hanoi(4)
3. floodFill
  Python code: notes-recursion-floodFill-grid-based.py
  Key excerpt:
  def floodFill(data, row, col, depth=0): if ((row < 0) or (row >= data.rows) or (col < 0) or (col >= data.cols)): return # off-board! cell = data.cells[row][col] if (cell.isWall == True): return # hit a wall if (cell.depth >= 0): return # already been here # "fill" this cell cell.depth = depth cell.ordinal = len(data.floodFillOrder) data.floodFillOrder.append(cell) # then recursively fill its neighbors floodFill(data, row-1, col, depth+1) floodFill(data, row+1, col, depth+1) floodFill(data, row, col-1, depth+1) floodFill(data, row, col+1, depth+1)

Using Recursive Results
1. powerset
  
  def powerset(a): # returns a list of all subsets of the list a if (len(a) == 0): return [[]] else: allSubsets = [ ] for subset in powerset(a[1:]): allSubsets += [subset] allSubsets += [[a[0]] + subset] return allSubsets print(powerset([1,2,3]))
2. permutations
  
  def permutations(a): # returns a list of all permutations of the list a if (len(a) == 0): return [[]] else: allPerms = [ ] for subPermutation in permutations(a[1:]): for i in range(len(subPermutation)+1): allPerms += [subPermutation[:i] + [a[0]] + subPermutation[i:]] return allPerms print(permutations([1,2,3]))

Applications of Recursion
1. Recursive Sorting
  1. Mergesort
    
    def merge(A, B): # beautiful, but impractical for large N if ((len(A) == 0) or (len(B) == 0)): return A+B else: if (A[0] < B[0]): return [A[0]] + merge(A[1:], B) else: return [B[0]] + merge(A, B[1:]) def merge(A, B): # iterative (ugh) and destructive (double ugh), but practical... C = [ ] i = j = 0 while ((i < len(A)) or (j < len(B))): if ((j == len(B)) or ((i < len(A)) and (A[i] <= B[j]))): C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 return C def mergesort(L): if (len(L) < 2): return L else: mid = len(L)//2 left = mergesort(L[:mid]) right = mergesort(L[mid:]) return merge(left, right) print(mergesort([1,5,3,4,2,0]))
  2. Quicksort
    
    def quicksort(L): if (len(L) < 2): return L else: first = L[0] # pivot rest = L[1:] lo = [x for x in rest if x < first] hi = [x for x in rest if x >= first] return quicksort(lo) + [first] + quicksort(hi) print(quicksort([1,5,3,4,2,0]))
2. File System Navigation
  1. printFiles
    
    import os def printFiles(path): if (os.path.isdir(path) == False): # base case: not a folder, but a file, so print its path print(path) else: # recursive case: it's a folder for filename in os.listdir(path): printFiles(path + "/" + filename) # To test this, download and expand this zip file in the same directory # as the Python file you are running: colab10_sampleFiles.zip # 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. printFiles("sampleFiles")
  2. listFiles
    
    import os def listFiles(path): if (os.path.isdir(path) == False): # base case: not a folder, but a file, so return singleton list with its path return [path] else: # recursive case: it's a folder, return list of all paths files = [ ] for filename in os.listdir(path): files += listFiles(path + "/" + filename) return files # To test this, download and expand this zip file in the same directory # as the Python file you are running: colab10_sampleFiles.zip print(listFiles("sampleFiles"))
3. Fractals
  1. kochSnowflake
    Python code: notes-recursion-koch-snowflake.py
    Key excerpt:
    def kochSide(length, n): if (n == 1): turtle.forward(length) else: kochSide(length/3.0, n-1) turtle.left(60) kochSide(length/3.0, n-1) turtle.right(120) kochSide(length/3.0, n-1) turtle.left(60) kochSide(length/3.0, n-1)
  2. sierpinskiTriangle
    Python code: notes-recursion-sierpinsky-triangle.py
    Key excerpt:
    def drawSierpinskyTriangle(canvas, x, y, size, level): # (x,y) is the lower-left corner of the triangle # size is the length of a side if (level == 0): canvas.create_polygon(x, y, x+size, y, x+size/2, y-size*(3**0.5)/2, fill="black") else: drawSierpinskyTriangle(canvas, x, y, size/2, level-1) drawSierpinskyTriangle(canvas, x+size/2, y, size/2, level-1) drawSierpinskyTriangle(canvas, x+size/4, y-size*(3**0.5)/4, size/2, level-1)

Backtracking
Sometimes, when problem solving, you'll encounter a problem that has several parts which each have several possible solutions. One way to find a set of solution-parts that all work together is to use backtracking. This process follows the following template:
# General backtracking template def solveWithBacktracking(problemState): if isComplete(problemState): return problemState nextStep = getNextStep(problemState) for move in getPossibleMoves(problemState, nextStep): # Sometimes it's easier to make a move, then check if it's valid. # Sometimes it's easier to check if a move is valid first. # Just make sure that you always undo a move properly! if isValid(problemState, nextStep, move): problemState = makeMove(problemState, nextStep, move) tmpSolution = solveWithBacktracking(problemState) if tmpSolution != None: return tmpSolution problemState = undoMove(problemState, nextStep, move) return None
1. maze solving
  Python code: notes-recursion-maze-solver.py
  Key excerpt:
  def isValid(data, row,col,direction): maze = data.maze rows,cols = len(maze),len(maze[0]) if not (0<=row<rows and 0<=col<cols): return False if direction==EAST: return maze[row][col].east if direction==SOUTH: return maze[row][col].south if direction==WEST: return maze[row][col-1].east if direction==NORTH: return maze[row-1][col].south assert False def solve(data, row, col, visited): # base cases if row == len(data.maze)-1 and col == len(data.maze[0])-1: return visited # recursive case for direction in [NORTH,SOUTH,EAST,WEST]: drow, dcol = direction if (row+drow, col+dcol) not in visited and \ isValid(data, row, col, direction): visited.add((row+drow,col+dcol)) tmpSolution = solve(data, row+drow, col+dcol, visited) if tmpSolution != None: return tmpSolution visited.remove((row+drow,col+dcol)) return None def solveMaze(data): visited = set() visited.add((0, 0)) return solve(data, 0, 0, visited)
2. nQueens
  
  def isLegal(board, queenRow, queenCol): # A board is legal if no two queens can attack each other # We only need to check the most recently placed queen for row in range(len(board)): for col in range(len(board[0])): if queenRow == row and queenCol == col: continue elif board[row][col] == "Q": if ((queenRow == row) or (queenCol == col) or (queenRow + queenRow == row + col) or (queenRow - queenCol == row - col)): return False return True def solve(board, row): if (row == len(board)): return board else: for col in range(len(board[row])): board[row][col] = "Q" if isLegal(board, row, col): solution = solve(board, row + 1) if (solution != None): return solution board[row][col] = " " return None def printBoard(board): for row in range(len(board)): print("".join(board[row])) def nQueens(n): board = [ [" "] * n for row in range(n) ] solution = solve(board, 0) if solution != None: printBoard(solution)

Improving Efficiency with Memoization
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("fib(%2d) = %8d, time =%5dms" % (n, fibOfN, 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("fib(%2d) = %8d, time =%5dms" % (n, fibOfN, ms)) testFib() # ahhh, much better!
3. A more elegant solution:
  def memoized(f): # You are not responsible for how this decorator works # on the inside, just how to 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("fib(%2d) = %8d, time =%5dms" % (n, fibOfN, ms)) testFib() # ahhh, much better!

Expanding the Stack Size and Recursion Limit
1. The problem:
  def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) print(rangeSum(1,1234)) # RuntimeError: maximum recursion depth exceeded
2. The solution (on most platforms):
  def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) def callWithLargeStack(f,*args): import sys import threading threading.stack_size(2**27) # 64MB stack sys.setrecursionlimit(2**27) # will hit 64MB stack limit first # need new thread to get the redefined stack size def wrappedFn(resultWrapper): resultWrapper[0] = f(*args) resultWrapper = [None] #thread = threading.Thread(target=f, args=args) thread = threading.Thread(target=wrappedFn, args=[resultWrapper]) thread.start() thread.join() return resultWrapper[0] print(callWithLargeStack(rangeSum,1,123456)) # prints 7620753696
3. The "solution" (on some Macs):
  def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) def callWithLargeStack(f,*args): import sys import threading sys.setrecursionlimit(2**14) # max recursion depth of 16384 isWindows = (sys.platform.lower() in ["win32", "cygwin"]) if (not isWindows): return f(*args) # sadness... threading.stack_size(2**27) # 64MB stack # need new thread to get the redefined stack size def wrappedFn(resultWrapper): resultWrapper[0] = f(*args) resultWrapper = [None] #thread = threading.Thread(target=f, args=args) thread = threading.Thread(target=wrappedFn, args=[resultWrapper]) thread.start() thread.join() return resultWrapper[0] print(callWithLargeStack(rangeSum,1,123456)) # prints 7620753696

CMU 15-112: Fundamentals of Programming and Computer Science Class Notes: Recursion (Continued)

CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion (Continued)