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. Using Multiple Recursive Calls
    1. fibonacci
    2. towersOfHanoi
  10. Using Recursive Results
    1. powerset
    2. permutations
  11. More Examples
  12. Iteration vs Recursion Summary

  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

  6. Multiple Base/Recursive Case Examples
    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

    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]

  7. Recursive Debugging
  8. # 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))

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

  10. Using 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
      def moveDiscs(pegs, startPeg, endPeg, tmpPeg, numDiscs): # If you have only one disc, just move it! if numDiscs == 1: assert(len(pegs[endPeg]) == 0 or pegs[startPeg][0] < pegs[endPeg][0]) disc = pegs[startPeg].pop(0) print("Moving", disc, "from", startPeg, "to", endPeg) pegs[endPeg].insert(0, disc) return 1 else: numMoves = 0 # If you want to move N discs, move the top N-1 discs to the tmp peg numMoves += moveDiscs(pegs, startPeg, tmpPeg, endPeg, numDiscs - 1) # Then move the bottom disc to the end peg numMoves += moveDiscs(pegs, startPeg, endPeg, tmpPeg, 1) # Then move the N-1 discs from the tmp to the end peg numMoves += moveDiscs(pegs, tmpPeg, endPeg, startPeg, numDiscs - 1) return numMoves # A wrapper function that sets up the other parameters based on pegs def towersOfHanoi(pegs): return moveDiscs(pegs, "left", "right", "middle", len(pegs["left"])) pegs = { "left" : [1, 2, 3], "middle" : [], "right" : [] } print("Number of discs moved:", towersOfHanoi(pegs)) print("End peg state:", pegs)

  11. Using Recursive Results
    1. powerset
      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]))

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

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