CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion: Worked Examples

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