Computer Science 15-112, Fall 2011
Class Notes:  Recursion

  1. Popular Recursion
  2. General Recursive Form
  3. Basic Examples
    1. rangeSum
    2. listSum
    3. power
    4. interleave
  4. Examples with Multiple Base or Recursive Cases
    1. power with negative exponents
    2. interleave with different-length lists
  5. Examples with Multiple Recursive Calls
    1. fibonacci
    2. towersOfHanoi
  6. Examples Comparing Iteration and Recursion
    1. factorial
    2. reverse
    3. gcd
  7. Iteration vs Recursion Summary
  8. Expanding the Stack Size and Recursion Limit (callWithLargeStack)
  9. Improving Efficiency with Memoization
  10. Some Interesting Recursion Examples
    1. powerset (all subsets)
    2. permutations
    3. printFiles (with os module)
    4. listFiles (with os module)
    5. floodFill (with PhotoImage pixels)
    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
    8. Backtracking
      1. maze solving
      2. nQueens
  11. More Advanced Recursion Examples

Recursion

  1. Popular Recursion
    1. "Recursion":  See "Recursion".
    2. Google search: Recursion
    3. Recursion comic:  http://xkcd.com/244/
    4. Droste Effect:  See the Wikipedia page and this Google image search
    5. Fractals:  See the Wikipedia page and this Google image search and this infinitely-zooming video
    6. The Chicken and Egg Problem  (mutual recursion)
    7. Sourdough Recipe:  First, start with some sourdough, then...
    8. Books:   Godel, Escher, Bach;  Metamagical Themas;
       
  2. General Recursive Form
    def recursiveFunction():
    if (this is the base case):
        # no recursion allowed here!
        do something non-recursive
    else:
        # this is the recursive case!
        do something recursive

    
    See http://en.wikipedia.org/wiki/Recursion_(computer_science)
  3. Basic Examples
    1. rangeSum
      def rangeSum(lo, hi):
    if (lo > hi):
        return 0
    else:
        return lo + rangeSum(lo+1, hi)

print rangeSum(10,15) # 75
    2. listSum
      def listSum(list):
    if (len(list) == 0):
        return 0
    else:
        return list[0] + listSum(list[1:])

print listSum([2,3,5,7,11]) # 28
    3. power
      def power(base, expt):
    # assume expt is non-negative integer
    if (expt == 0):
        return 1
    else:
        return base * power(base, expt-1)

print power(2,5) # 32
    4. interleave
      def interleave(list1, list2):
    # assume list1 and list2 are same-length lists
    if (len(list1) == 0):
        return []
    else:
        return [list1[0] , list2[0]] + interleave(list1[1:], list2[1:])

print interleave([1,2,3],[4,5,6])
  4. Examples with Multiple Base or Recursive Cases
    1. power with negative exponents
      def power(base, expt):
    # This version allows for negative exponents
    # It still assumes that expt is an integer, however.
    if (expt == 0):
        return 1
    elif (expt < 0):
        return 1.0/power(base,abs(expt))
    else:
        return base * power(base, expt-1)

print power(2,5) # 32
print power(2,-5) # 1/32 = 0.03125
    2. interleave with different-length lists
      def interleave(list1, list2):
    # This version allows for different-length lists
    if (len(list1) == 0):
        return list2
    elif (len(list2) == 0):
        return list1
    else:
        return [list1[0] , list2[0]] + interleave(list1[1:], list2[1:])

print interleave([1,2,3],[4,5,6,7,8])
  5. Examples with Multiple Recursive Calls
    1. fibonacci

      A)  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)

for n in range(15): print fib(n),

      B) 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)

      C) 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)

      D) 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

      A)  First attempt (without Python)
      # This is the plan we generated in class to solve Towers of Hanoi:
magically move(n-1, frm, via, to)
          move(  1, frm, to,  via)
magically move(n-1, via, to,  frm)

      B)  Turn into Python (The "magic" is recursion!)

      def move(n, frm, to, via):
    move(n-1, frm, via, to)
    move(  1, frm, to,  via)
    move(n-1, via, to,  frm)

move(2, 0, 1, 2) # Does not work -- infinite recursion

      C)  Once again, with a base case

      def move(n, frm, to, via):
    if (n == 1):
        print (frm, to),
    else:
        move(n-1, frm, via, to)
        move(  1, frm, to,  via)
        move(n-1, via, to,  frm)

move(2, 0, 1, 2)

      D)  Once more, with a nice wrapper:

      def move(n, frm, to, via):
    if (n == 1):
        print (frm, to),
    else:
        move(n-1, frm, via, to)
        move(  1, frm, to,  via)
        move(n-1, via, to,  frm)

def hanoi(n):
    print "Solving Towers of Hanoi with n =",n
    move(n, 0, 1, 2)
    print

hanoi(4)

      E)  And again, printing call stack and recursion depth:

      def move(n, frm, to, via, depth=0):
    print (" " * 3 * depth), "move", n, "from", frm, "to", to, "via", via
    if (n == 1):
        print (" " * 3 * depth), (frm, to)
    else:
        move(n-1, frm, via, to, depth+1)
        move(1, frm, to, via, depth+1)
        move(n-1, via, to, frm, depth+1)
      def hanoi(n):
    print "Solving Towers of Hanoi with n =",n
    move(n, 0, 1, 2)
    print
      hanoi(4)

      F) Iterative Towers of Hanoi (just to see it's possible)
      For a good explanation of iterative solutions to Towers of Hanoi, look at this part of the Towers of Hanoi Wikipedia page.

      def iterativeHanoi(n):
    def f(k): return (k%3) if (n%2==0) else (-k%3)
    return [(f(move&(move-1)), f((move|(move-1))+1)) for move in xrange(1,1<<n)]

def recursiveHanoi(n, frm=0, to=1, via=2):
    if (n == 1):
        return [(frm, to)]
    else:
        return (recursiveHanoi(n-1, frm, via, to) +
                recursiveHanoi(  1, frm, to,  via) +
                recursiveHanoi(n-1, via, to,  frm))

def compareIterativeAndRecursiveHanoi():
    for n in xrange(1,20):
        assert(iterativeHanoi(n) == recursiveHanoi(n))
    print "iterative and recursive solutions match exactly in all tests!"

compareIterativeAndRecursiveHanoi()

      G) Towers of Hanoi animation
      This is fun and interesting:  hanoiAnimation.py

  6. Examples Comparing Iteration and Recursion
    Function Iterative Solution Recursive Solution Recursive Solution with Stack Trace
    factorial def factorial(n):
        factorial = 1
        for i in range(2,n+1):
            factorial *= i
        return factorial

    print factorial(5)


    		 def factorial(n):
        if (n < 2):
            return 1
        else:
            return n*factorial(n-1)

    print factorial(5)


    		 def factorial(n, depth=0):
        print "   "*depth, "factorial(",n,"):"
        if (n < 2):
            result = 1
        else:
            result = n*factorial(n-1,depth+1)
        print "   "*depth, "-->", result
        return result

    print factorial(5)
    reverse def reverse(s):
        reverse = ""
        for ch in s:
            reverse = ch + reverse
        return reverse

    print reverse("abcd")


    		 def reverse(s):
        if (s == ""):
            return ""
        else:
            return reverse(s[1:]) + s[0]

    print reverse("abcd")


    		 def reverse(s, depth=0):
        print "   "*depth, "reverse(",s,"):"
        if (s == ""):
            result = ""
        else:
            result = reverse(s[1:], depth+1) + s[0]
        print "   "*depth, "-->", result
        return result

    print reverse("abcd")
    gcd def gcd(x,y):
        while (y > 0):
            oldX = x
            x = y
            y = oldX % y
        return x

    print gcd(500, 420) # 20

    		 def gcd(x,y):
        if (y == 0):
            return x
        else:
            return gcd(y,x%y)

    print gcd(500, 420) # 20


    		 def gcd(x,y,depth=0):
        print "   "*depth, "gcd(",x, ",", y, "):"
        if (y == 0):
            result = x
        else:
            result = gcd(y,x%y,depth+1)
        print "   "*depth, "-->", result
        return result

    print gcd(500, 420) # 20

  7. Iteration vs Recursion Summary
    Recursion Iteration
    Elegance ++ --
    Performance -- ++
    Debugability -- ++

    Note:  These are general guidelines.   For example, it is possible to use recursion with high performance, and it is certainly possible to use (or abuse) iteration with very low performance.

    Conclusion (for now):  Use iteration when practicable.  Use recursion when required (for "naturally recursive problems").
     
  8. 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
      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
  9. 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 xrange(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. The solution
      def memoized(f):
    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 xrange(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!
  10. Some Interesting Recursion Examples
    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 xrange(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")

Produces this output:

sampleFiles/emergency.txt
sampleFiles/folderA/fishing.txt
sampleFiles/folderA/folderC/folderD/misspelled.txt
sampleFiles/folderA/folderC/folderD/penny.txt
sampleFiles/folderA/folderC/folderE/tree.txt
sampleFiles/folderA/folderC/giftwrap.txt
sampleFiles/folderA/widths.txt
sampleFiles/folderB/folderH/driving.txt
sampleFiles/folderB/restArea.txt
sampleFiles/mirror.txt
    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")

Produces this output:

['sampleFiles/emergency.txt', 'sampleFiles/folderA/fishing.txt', 'sampleFiles/fo
lderA/folderC/folderD/misspelled.txt', 'sampleFiles/folderA/folderC/folderD/penn
y.txt', 'sampleFiles/folderA/folderC/folderE/tree.txt', 'sampleFiles/folderA/fol
derC/giftwrap.txt', 'sampleFiles/folderA/widths.txt', 'sampleFiles/folderB/folde
rH/driving.txt', 'sampleFiles/folderB/restArea.txt', 'sampleFiles/mirror.txt']
    5. floodFill (with PhotoImage pixels)

      A)  Pixel-based FloodFill without animation

      Python code:  floodFill-pixel-based.py  (may have problems on some Macs)
      Key excerpt:
      def floodFill(x, y, color):
    if ((not inImage(x,y)) or (getColor(img, x, y) == color)):
        return
    img.put(color, to=(x, y))
    floodFill(x-1, y, color)
    floodFill(x+1, y, color)
    floodFill(x, y-1, color)
    floodFill(x, y+1, color)
      B)  Grid-based FloodFill with animation

      Python code:  floodFill-grid-based.py
      Key excerpt:

      def floodFill(row, col, color, depth=0):
    if ((row >= 0) and (row < canvas.data.rows) and
        (col >= 0) and (col < canvas.data.cols) and
        (canvas.data.board[row][col] != color)):
        canvas.data.board[row][col] = color
        canvas.data.depth[row][col] = depth
        redrawAll()
        canvas.update()
        time.sleep(0.05 if (depth < 25) else 0.005)
        floodFill(row-1, col, color, depth+1)
        floodFill(row+1, col, color, depth+1)
        floodFill(row, col-1, color, depth+1)
        floodFill(row, col+1, color, depth+1)
    6. Fractals
      1. kochSnowflake (with Turtle)

        Python code:  koch-snowflake.py
        Key excerpt:
        def kN(length, n):
    if (n == 1):
        turtle.forward(length)
    else:
        kN(length/3.0, n-1)
        turtle.left(60)
        kN(length/3.0, n-1)
        turtle.right(120)
        kN(length/3.0, n-1)
        turtle.left(60)
        kN(length/3.0, n-1)

def kochSnowflake(length, n):
    for step in range(3):
        kN(length, n)
        turtle.right(120)
      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
    x = float(x)
    y = float(y)
    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
      See recursive-sorts.py
       
      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:])
      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
      3. merge sort
        def merge(A, B):
    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 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)
      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)
      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)
    8. Backtracking (solving mazes, Sudoku-like puzzles, and, in general, "constraint satisfaction problems")
      1. maze solving

        Python code:  mazeSolver.py
        Key excerpt:

            def solve(row,col):
        if (row,col) in visited:
            return False
        visited.add((row,col))
        if (row,col)==(targetRow,targetCol):
            return True
        for drow,dcol in [NORTH,SOUTH,EAST,WEST]:
            if isValid(row,col,(drow,dcol)):
                if solve(row+drow,col+dcol):
                    return True
        visited.remove((row,col))
        return False
      2. nQueens

        Problem:  Try to place N queens on an NxN chessboard so no two queens are attacking each other.
        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 xrange(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
            # darn, can't place the queen anywhere
            return None
    9. More Advanced Recursion Examples
      Note: some of these algorithms also have reasonably straightforward iterative formulations, or comparable iterative alternatives.
      1. Top-Down Dynamic Programming
        (Problem-solving by divide-and-conquer while reusing solutions to overlapping subproblems.  Many items in this list are really examples of Dynamic Programming.)
      2. Top-Down (Recursive Descent) Parsing
      3. Evaluating (Lisp-Like) Expressions
      4. String Matching (Longest common subsequence, ...)
      5. Bioinformatics (sequence alignment, ...)
      6. Music (beat tracking, dynamic time warping, ...)
      7. AI for 2-player board games (Minimax [with Alpha-Beta Pruning])
      8. Image Manipulation (seam carving,...)
      9. Math (Fast Fourier Transform, Fast Matrix Multiplication (Strassen), Fast Scalar Multiplication (Karatsuba), ...)
      10. And many, many others...

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem