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

1. Popular Recursion
2. General Recursive Form
3. Recursive Math
4. Basic Examples
   1. rangeSum
   2. listSum
   3. power
   4. interleave
5. Divide-And-Conquer Examples
   1. rangeSum
   2. listSum
   3. power
   4. interleave
6. Examples with Multiple Base or Recursive Cases
   1. power with negative exponents
   2. interleave with different-length lists
7. Examples with Multiple Recursive Calls
   1. fibonacci
   2. towersOfHanoi
8. Examples Comparing Iteration and Recursion
   1. factorial
   2. reverse
   3. gcd
9. Iteration vs Recursion Summary
10. Expanding the Stack Size and Recursion Limit (callWithLargeStack)
11. Improving Efficiency with Memoization
12. Advanced Worked Examples Using 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;
   9. Wikipedia page on Recursion: See here.


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


3. Recursive Math
   
   # 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()


4. 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(L): if (len(L) == 0): return 0 else: return L[0] + listSum(L[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 (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]


5. Divide-And-Conquer Examples
   
   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
   
   
   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
   
   
   3. power
      def power(base, expt): # assume expt is non-negative integer if (expt == 0): return 1 elif (expt % 2 == 0): return power(base, expt//2)**2 else: return base * power(base, expt//2)**2 print(power(2,5)) # 32
   
   
   4. interleave
      def interleave(list1, list2): # assume list1 and list2 are same-length lists if (len(list1) == 0): return [] elif (len(list1) == 1): return [list1[0], list2[0]] else: mid = len(list1)//2 return (interleave(list1[:mid], list2[:mid]) + interleave(list1[mid:], list2[mid:])) print(interleave([1,2,3],[4,5,6])) # [1,4,2,5,3,6]


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


7. Examples with Multiple Recursive Calls
   1. fibonacci
      
      1. 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) print([fib(n) for n in range(15)])
      
      
      2. 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)
      
      
      3. 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)
      
      
      4. 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
      
      1. First attempt (without Python):
         # This is the plan to solve Towers of Hanoi (based on magic!) magically move(n-1, source, temp, target) move( 1, source, target, temp) magically move(n-1, temp, target, source)
      
      
      2. Turn into Python (The "magic" is recursion!):
         def move(n, source, target, temp): move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) move(2, 0, 1, 2) # Does not work -- infinite recursion
      
      
      3. Once again, with a base case:
         def move(n, source, target, temp): if (n == 1): print((source, target), end="") else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) move(2, 0, 1, 2)
      
      
      4. Once more, with a nice wrapper:
         def move(n, source, target, temp): if (n == 1): print((source, target), end="") else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) def hanoi(n): print("Solving Towers of Hanoi with n =", n) move(n, 0, 1, 2) print() hanoi(4)
      
      
      5. And again, printing call stack and recursion depth:
         def move(n, source, target, temp, depth=0): print((" " * 3 * depth), "move", n, "from", source, "to", target, "via", temp) if (n == 1): print((" " * 3 * depth), (source, target)) else: move(n-1, source, temp, target, depth+1) move( 1, source, target, temp, depth+1) move(n-1, temp, target, source, depth+1) def hanoi(n): print("Solving Towers of Hanoi with n =", n) move(n, 0, 1, 2) print() hanoi(4)
      
      
      6. Iterative Towers of Hanoi (just to see it's possible):
         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 range(1,1 << n)] def recursiveHanoi(n, source=0, target=1, temp=2): if (n == 1): return [(source, target)] else: return (recursiveHanoi(n-1, source, temp, target) + recursiveHanoi( 1, source, target, temp) + recursiveHanoi(n-1, temp, target, source)) def compareIterativeAndRecursiveHanoi(): for n in range(1,10): assert(iterativeHanoi(n) == recursiveHanoi(n)) print("iterative and recursive solutions match exactly in all tests!") compareIterativeAndRecursiveHanoi()


8. 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 (len(s) < 2): return s else: mid = len(s)//2 return (reverse(s[mid:]) + reverse(s[:mid])) print(reverse("abcd"))	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"))
   gcd	def gcd(x,y): while (y > 0): (x, y) = (y, x%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



9. Iteration vs Recursion Summary
   

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


11. 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!


12. Advanced Worked Examples Using Recursion
    See here.