15-112
Fall-17

Home

Syllabus

Schedule

Piazza

Autolab

Gallery

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