CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Recursion (Getting Started)

1. Popular Recursion
2. General Recursive Form
3. Recursive Math
4. Recursive Debugging
5. Basic Examples
   1. rangeSum
   2. listSum
   3. power
   4. interleave
6. Divide-And-Conquer Examples
   1. rangeSum
   2. listSum
7. Multiple Base/Recursive Case Examples
   1. power
   2. interleave
8. Examples Comparing Iteration and Recursion
   1. factorial
   2. reverse
   3. gcd
9. Iteration vs Recursion Summary
10. More Examples

1. Popular Recursion   video
   
   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;
   9. Wikipedia page on Recursion: See here.


2. General Recursive Form   video
   

   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



3. Recursive Math   video
   

   # A few example recursive functions.
   # Can you figure out what each one does, in general?
   
   import math
   
   def f1(x):
       if (x == 0): return 0
       else: return 1 + f1(x-1)
   
   def f2(x):
       if (x == 0): return 40
       else: return 1 + f2(x-1)
   
   def f3(x):
       if (x == 0): return 0
       else: return 2 + f3(x-1)
   
   def f4(x):
       if (x == 0): return 40
       else: return 2 + f4(x-1)
   
   def f5(x):
       if (x == 0): return 0
       else: return x + f5(x-1) # why does this work?
   
   def f6(x):
       if (x == 0): return 0
       else: return 2*x-1 + f6(x-1) # why does this work?
   
   def f7(x):
       if (x == 0): return 1
       else: return 2*f7(x-1)
   
   def f8(x):
       if (x < 2): return 0
       else: return 1 + f8(x//2)
   
   def f9(x):
       if (x < 2): return 1
       else: return f9(x-1) + f9(x-2)
   
   def f10(x):
       if (x == 0): return 1
       else: return x*f10(x-1)
   
   def f11(x, y):
       if (y < 0): return -f11(x, -y)
       elif (y == 0): return 0
       else: return x + f11(x, y-1)
   
   def f12(x,y):
       if ((x < 0) and (y < 0)): return f12(-x,-y)
       elif ((x == 0) or (y == 0)): return 0
       else: return x+y-1 + f12(x-1, y-1)  # why does this work?
   
   def f13(L):
       assert(type(L) == list)
       if (len(L) < 2): return [ ]
       else: return f13(L[2:]) + [L[1]]
   
   def go():
       while True:
           n = input("Enter function # (1-13, or 0 to quit): ")
           if (n == "0"): break
           elif (n == "11"): print("f11(5, 7) ==", f11(5, 7))
           elif (n == "12"): print("f12(5, 7) ==", f12(5, 7))
           elif (n == "13"): print("f13(list(range(20))) ==", f13(list(range(20))))
           else:
               f = globals()["f"+n]
               print("f"+n+": ", [f(x) for x in range(10)])
           print()
   
   go()

   Select


4. Basic Examples   video
   
   1. rangeSum

      def rangeSum(lo, hi):
          if (lo > hi):
              return 0
          else:
              return lo + rangeSum(lo+1, hi)
      
      print(rangeSum(10,15)) # 75

      Select Visualize Run
   
   
   2. listSum

      def listSum(L):
          if (len(L) == 0):
              return 0
          else:
              return L[0] + listSum(L[1:])
      
      print(listSum([2,3,5,7,11])) # 28

      Select Visualize Run
   
   
   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

      Select Visualize Run
   
   
   4. interleave

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

      Select Visualize Run


5. Divide-And-Conquer Examples   video
   
   1. rangeSum

      def rangeSum(lo, hi):
          if (lo == hi):
              return lo
          else:
              mid = (lo + hi)//2
              return rangeSum(lo, mid) + rangeSum(mid+1, hi)
      
      print(rangeSum(10,15)) # 75

      Select Visualize Run
   
   
   2. listSum

      def listSum(L):
          if (len(L) == 0):
              return 0
          elif (len(L) == 1):
              return L[0]
          else:
              mid = len(L)//2
              return listSum(L[:mid]) + listSum(L[mid:])
      
      print(listSum([2,3,5,7,11])) # 28

      Select Visualize Run


6. Multiple Base/Recursive Case Examples   video
   
   1. power

      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

      Select Visualize Run
   
   
   2. interleave

      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])) # [1,3,2,4,5,6]

      Select Visualize Run


7. Recursive Debugging

# Debugging recursive code can get tricky! We can make it easier by keeping track
# of the recursion depth using a parameter, then adjusting the print based on that depth.
# We'll make the parameter optional (giving it a starting value) so that it
# doesn't need to be included when the function is called.

def rangeSum(lo, hi, depth=0):
    print("   " * depth + "rangeSum(" + str(lo) + ", " + str(hi) + ")")
    if (lo > hi):
        result = 0
    else:
        result = lo + rangeSum(lo + 1, hi, depth + 1)
    print("   " * depth + "-->", result)
    return result

print(rangeSum(10, 15))

Select Visualize Run


8. Examples Comparing Iteration and Recursion   video
   

   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)) Select Visualize Run	def factorial(n): if (n < 2): return 1 else: return n*factorial(n-1) print(factorial(5)) Select Visualize Run	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)) Select Visualize Run
   reverse	def reverse(s): reverse = "" for ch in s: reverse = ch + reverse return reverse print(reverse("abcd")) Select Visualize Run	def reverse(s): if (len(s) < 2): return s else: mid = len(s)//2 return (reverse(s[mid:]) + reverse(s[:mid])) print(reverse("abcd")) Select Visualize Run	def reverse(s, depth=0): print(" "*depth, "reverse(",s,"):") if (len(s) < 2): result = s else: mid = len(s)//2 result = (reverse(s[mid:], depth+1) + reverse(s[:mid], depth+1)) print(" "*depth, "-->", result) return result print(reverse("abcd")) Select Visualize Run
   gcd	def gcd(x,y): while (y > 0): (x, y) = (y, x%y) return x print(gcd(500, 420)) # 20 Select Visualize Run	def gcd(x,y): if (y == 0): return x else: return gcd(y,x%y) print(gcd(500, 420)) # 20 Select Visualize Run	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 Select Visualize Run



9. Iteration vs Recursion Summary   video
   

   	Recursion	Iteration
   Elegance
   Performance
   Debuggability

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


10. More Examples
    See these notes for more examples of how recursion can be used.