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

1. Expanding the Stack Size and Recursion Limit (callWithLargeStack)
2. Improving Efficiency with Memoization
3. Advanced Worked Examples Using Recursion
   1. powerset (all subsets)
   2. permutations
   3. printFiles (with os module)
   4. listFiles (with os module)
   5. floodFill (grid-based)
   6. Fractals
      1. kochSnowflake (with Turtle)
      2. sierpinskiTriangle (with Tkinter)
   7. Recursive Sorting
      1. selection sort
      2. insertion sort
      3. merge sort
      4. quick sort
      5. radix sort
      6. all these sorts with timing
   8. Backtracking
      1. maze solving
      2. nQueens

1. Expanding the Stack Size and Recursion Limit (callWithLargeStack)
   
   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


2. 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!


3. Advanced Worked Examples Using Recursion
   
   1. powerset (all subsets)
      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]))
   
   
   3. printFiles (with os module)
      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: 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), # download removeDsStore.py, place it in the same directory, and run it, # and you should see your .DS_Store files removed. printFiles("sampleFiles")
   
   
   4. listFiles (with os module)
      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: sampleFiles.zip print(listFiles("sampleFiles"))
   
   
   5. floodFill (grid-based)
      Python code: 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)
   
   
   6. Fractals
      1. kochSnowflake (with Turtle)
         Python code: 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 (with Tkinter)
         Python code: 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)
   
   
   7. Recursive Sorting
      1. selection sort
         def selectionsort(L): if (len(L) < 2): return L else: i = L.index(min(L)) return [L[i]] + selectionsort(L[:i] + L[i+1:]) print(selectionsort([1,5,3,4,2,0]))
      
      
      2. insertion sort
         def insertionsort(L): if (len(L) < 2): return L else: first = L[0] rest = insertionsort(L[1:]) lo = [x for x in rest if x < first] hi = [x for x in rest if x >= first] return lo + [first] + hi print(insertionsort([1,5,3,4,2,0]))
      
      
      3. merge sort
         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]))
      
      
      4. quick sort
         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]))
      
      
      5. radix sort
         def radixsort(L): # Only works for lists of non-negative integers! maxValue = max(L) def rsort(L, digitSelector): if (digitSelector > maxValue): return L else: zeroes = [x for x in L if (x & digitSelector == 0)] ones = [x for x in L if (x & digitSelector != 0)] return rsort(zeroes + ones, digitSelector << 1) return rsort(L, 1) print(radixsort([1,5,3,4,2,0]))
      
      
      6. all these sorts with timing
         See recursive-sorts.py.
   
   
   8. 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