Computer Science 15-110, Fall 2010
Class Notes:  Recursion Part 1

  1. General Recursive Form
  2. Examples
    1. fibonacci
    2. towersOfHanoi
    3. listFiles
    4. floodFill (with PhotoImage pixels)
    5. kochSnowflake (with Turtle)
    6. sierpinskiTriangle (with Tkinter)
  3. Recursion vs Iteration
  4. Counterexamples
    1. factorial
    2. reverse
    3. gcd

Recursion Part 1

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

  2. Examples

    1. fibonacci

      A)  First attempt

      # Note: as written, this function is very inefficient!
      # (We need to use "memoization" to speed it up, which we'll learn later!)
      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)

    3. listFiles

      import os
      def listFiles(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):
                  listFiles(path + "/" + filename)

      # To test this, download and expand this zip file in the same directory
      # as the Python file you are running:
      # https://www.cs.cmu.edu/~110/handouts/hw5TestFolder.zip

      listFiles("hw5TestFolder")

      Produces this output:

      hw5TestFolder/emergency.txt
      hw5TestFolder/folderA/fishing.txt
      hw5TestFolder/folderA/folderC/folderD/misspelled.txt
      hw5TestFolder/folderA/folderC/folderD/penny.txt
      hw5TestFolder/folderA/folderC/folderE/tree.txt
      hw5TestFolder/folderA/folderC/giftwrap.txt
      hw5TestFolder/folderA/widths.txt
      hw5TestFolder/folderB/folderH/driving.txt
      hw5TestFolder/folderB/restArea.txt
      hw5TestFolder/mirror.txt

    4. floodFill (with PhotoImage pixels)

      A) Basic idea

      def floodFill(x, y, color):
          if ((not inImage(x,y)) or (getColor(img, x, y) == color)):
              # do nothing in the base case!
              pass
          else:
              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)  Full Program

      # FloodFill using Tkinter

      from Tkinter import *
      root = Tk()
      canvas = Canvas(root, width=250, height=250)
      canvas.pack()

      canvas.create_text(125,20,text="FloodFill Demo",font="Helvetica 16 bold")
      canvas.create_text(125,40,text="left click = draw",font="Helvetica 12 italic")
      canvas.create_text(125,60,text="shift-left or right click = fill",font="Helvetica 12 italic")

      imgLeft = 75
      imgTop = 75
      imgWidth = 100
      imgHeight = 100

      img = PhotoImage(width=imgWidth, height=imgHeight)
      canvas.create_image(imgLeft, imgTop, image=img, anchor=NW)

      color1 = "#0000ff"
      color2 = "#00ff00"
      canvas.fillColor = color1
      for x in range(imgWidth):
          for y in range(imgHeight):
              img.put(color1, to=(x,y))

      def inImage(x, y):
          return ((x >= 0) and (x < imgWidth) and \
                  (y >= 0) and (y < imgHeight))

      def drawDot(x, y, color):
          r = 5
          for dx in range(-r,+r):
              for dy in range(-r,+r):
                  if ((dx**2 + dy**2 <= r**2) and inImage(x+dx,y+dy)):
                      img.put(color, to=(x+dx,y+dy))

      def getColor(img, x, y):
          hexColor = "#%02x%02x%02x" % getRGB(img, x, y)
          return hexColor

      def getRGB(img, x, y):
          value = img.get(x, y)
          return tuple(map(int, value.split(" ")))

      def mousePressed(event, doFlood):
          x = event.x-imgLeft
          y = event.y-imgTop
          if (inImage(x,y)):
              color = getColor(img, x, y)
              if (color == color1):
                  canvas.fillColor = color2
              else:
                  canvas.fillColor = color1
              if (doFlood):
                 floodFillWithLargeStack(x, y)
              else:
                  drawDot(x, y, canvas.fillColor)
         
      def leftMousePressed(event):
          shiftDown = ((event.state & 0x0001) == 1)
          mousePressed(event, shiftDown)

      def leftMouseMoved(event):
          x = event.x-imgLeft
          y = event.y-imgTop
          if (inImage(x, y)):
              drawDot(x, y, canvas.fillColor)

      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)

      def floodFillWithLargeStack(x,y):
          import sys
          currentLimit = sys.getrecursionlimit()
          sys.setrecursionlimit(max(currentLimit, 10+imgWidth*imgHeight))
          import threading
          threading.stack_size(32*1024*1024)
          import thread
          thread.start_new_thread(floodFill,(x, y, canvas.fillColor))

      def rightMousePressed(event):
          mousePressed(event, True)
             
      canvas.bind("<Button-1>", leftMousePressed)
      canvas.bind("<B1-Motion>", leftMouseMoved)
      canvas.bind("<Button-3>", rightMousePressed)       
      root.mainloop()
       
    5. kochSnowflake (with Turtle)

      import turtle

      def k1(length):
          turtle.forward(length)

      def k2(length):
          turtle.forward(length/3.0)
          turtle.left(60)
          turtle.forward(length/3.0)
          turtle.right(120)
          turtle.forward(length/3.0)
          turtle.left(60)
          turtle.forward(length/3.0)

      def k2(length):
          k1(length/3.0)
          turtle.left(60)
          k1(length/3.0)
          turtle.right(120)
          k1(length/3.0)
          turtle.left(60)
          k1(length/3.0)   

      def k3(length):
          k2(length/3.0)
          turtle.left(60)
          k2(length/3.0)
          turtle.right(120)
          k2(length/3.0)
          turtle.left(60)
          k2(length/3.0)   

      def k4(length):
          k3(length/3.0)
          turtle.left(60)
          k3(length/3.0)
          turtle.right(120)
          k3(length/3.0)
          turtle.left(60)
          k3(length/3.0)   

      def kN(length, n):
          if (n == 0):
              k1(length) # same as:  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)

      turtle.delay(0)
      turtle.speed(0)
      turtle.penup()
      turtle.goto(-200,0)
      turtle.pendown()

      # kN(300, 4)  # same as k4
      kochSnowflake(300, 4)
      turtle.done()

      Alternate Derivation

      A) Non-Recursive Template

      # First attempt at Koch Snowflake using Python's turtle Package

      import turtle

      # This non-recursive function draws a simple Koch side.
      # This will be the template for the recursive case below (compare them!).
      def simpleKochSide(length):
          turtle.forward(length/3.0)
          turtle.right(60)
          turtle.forward(length/3.0)
          turtle.left(120)
          turtle.forward(length/3.0)
          turtle.right(60)
          turtle.forward(length/3.0)

      def simpleKochSnowflake(length):
          for step in range(3):
              simpleKochSide(length)
              turtle.left(120)

      turtle.penup()
      turtle.goto(-200, -100)
      turtle.setheading(0)
      turtle.pendown()
      turtle.delay(0)
      turtle.speed(0)
      simpleKochSnowflake(400)

      turtle.done()

      B) Recursive Version

      # Recursive Koch Snowflake using Python's turtle Package

      import turtle

      # This is the recursive version of drawing a side of the snowflake.
      # Here, if we are at the last level of recursion, we just move forward
      # (just like the simple case).  Otherwise, instead of calling forward,
      # we recursively call kochSide.  And that's how the magic happens!
      def kochSide(length, depth):
          if (depth == 0):
              turtle.forward(length)
          else:
              kochSide(length/3.0, depth-1)
              turtle.right(60)
              kochSide(length/3.0, depth-1)
              turtle.left(120)
              kochSide(length/3.0, depth-1)
              turtle.right(60)
              kochSide(length/3.0, depth-1)

      def kochSnowflake(length, recursionDepth):
          for step in range(3):
              kochSide(length,recursionDepth)
              turtle.left(120)

      turtle.penup()
      turtle.goto(-200, -100)
      turtle.setheading(0)
      turtle.pendown()
      turtle.delay(0)
      turtle.speed(0)

      kochSnowflake(400,2)
      from Tkinter import *
      import math
      turtle.done()

    6. sierpinskiTriangle (with Tkinter)

      from Tkinter import *
      import math
      def sierpinsky(canvas, x, y, size, level):
          x = float(x)
          y = float(y)
          if (level == 0):
              canvas.create_polygon(x, y,
                                    x+size, y,
                                    x+size/2, y-size*math.sqrt(3)/2,
                                    fill="black")
          else:
              sierpinsky(canvas, x, y, size/2, level-1)
              sierpinsky(canvas, x+size/2, y, size/2, level-1)
              sierpinsky(canvas, x+size/4, y-size*math.sqrt(3)/4, size/2, level-1)

      root = Tk()
      myCanvas = Canvas(root, width=500, height=500)
      myCanvas.pack()
      sierpinsky(myCanvas, 100, 400, 300, 2)
      root.mainloop()

  3. Recursion vs Iteration

    RecursionIteration
    Elegance++--
    Performance--++
    Debuggability--++

    Conclusion:  Use iteration when practicable.  Use recursion only when required (for naturally recursive problems).

  4. Counterexamples

    Function Iterative SolutionRecursive SolutionRecursive Solution with Stack Trace
    factorialdef 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)
    reversedef 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")
    gcddef 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

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