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

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 = f(*args) resultWrapper = [None] #thread = threading.Thread(target=f, args=args) thread = threading.Thread(target=wrappedFn, args=[resultWrapper]) thread.start() thread.join() return resultWrapper 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 = f(*args) resultWrapper = [None] #thread = threading.Thread(target=f, args=args) thread = threading.Thread(target=wrappedFn, args=[resultWrapper]) thread.start() thread.join() return resultWrapper 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] + 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] + 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 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 < B): return [A] + merge(A[1:], B) else: return [B] + 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 # 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]))

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