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

• Identify the base case(s) and recursive case(s) for a given problem.
• Recognize when it is more appropriate to use iteration or recursion.
• Write recursive code to solve problems.

1. Predict
2. General Recursive Form
3. Basic Examples
   1. listSum
   2. rangeSum
   3. power
4. Check 9.1
5. Multiple Base/Recursive Cases
   1. power
   2. interleave
6. Check 9.2
7. Practical Programming with Recursion
   1. Recursive Debugging
   2. Wrapper Functions
   3. Expanding the Stack Size and Recursion Limit
8. Check 9.3
9. Multiple Recursive Calls
   1. listSum
   2. fibonacci
   3. towersOfHanoi
   4. mergeSort
   5. quickSort
   6. floodFill
10. Combining Iteration and Recursion
    1. powerset
    2. permutations
11. Iteration vs. Recursion
    1. factorial
    2. reverse
    3. digitSum
    4. gcd
12. Popular Recursion

1. Predict
   Predict what the following code will output and write your guess in the editor.
   def f(n): if n == 0: return "boo!" else: print(n) return f(n-1) print(f(5))
   import sys def set_certificate(certificate_div_id, certificate): document[certificate_div_id].textContent = certificate def get_student_code(student_code_div_id): raw_student_code = document[student_code_div_id].textContent return window.patchCodeToCheckTimeout(raw_student_code, 'check_timeout();'); def make_certificate(student_code_div_id, certificate_div_id): student_code = get_student_code(student_code_div_id) certificate = [] output = "failure" if student_code != "": output = "success" certificate.append((output, type(output))) set_certificate(certificate_div_id, str(certificate))
   
   Compare
   Now run the code and see if you were right!
   def f(n): if n == 0: return "boo!" else: print(n) return f(n-1) print(f(5))


2. General Recursive Form
   Recursion is not a new data structure or a new piece of syntax. Instead, it is a new way to think about problem solving. It's especially useful for problems where options grow exponentially, like finding every possible combination of a set of items, or calculating a fibonacci number.
   
   In recursion, we divide a function into two possible cases: a base case, which returns the result for a known value, and a recursive case, which computes a result by calling the same function again on a smaller value.
   
   In other words- we solve the problem by assuming it's already solved!
   
   
   def recursiveFunction(): if (this is the base case): do something non-recursive else: do something recursive


3. Basic Examples
   In our basic examples, we have exactly one base case and exactly one recursive case, and each recursive case has exactly one recursive call.
   We could write these with loops instead, but it's useful to practice basic recursion this way.
   
   
   1. listSum
      # Problem: sum all of the numbers in a given list def listSum(L): # Base Case: the list is empty, so the sum is 0 if (len(L) == 0): return 0 else: # Recursive Case: assume we already know the sum of the entire list # after the first element. Add that sum to the first element. return L[0] + listSum(L[1:]) print(listSum([2,3,5,7,11])) # 28 # How do we know this code won't keep calling itself forever? # We always call listSum on a list that is SMALLER than the current list. # This means that the list must eventually reach the length 0. # We then catch it in the base case.
   
   
   2. rangeSum
      # Problem: sum all of the numbers from lo to hi, inclusive def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) print(rangeSum(10,15)) # 75
   
   
   3. power
      # Problem: raise the number base to the given exponent 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. Check 9.1


5. Multiple Base/Recursive Cases
   Sometimes, we need to include more than one base or recursive case when solving a problem. As long as the function only enters one condition per call, this should still work the same way as our basic 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): # new recursive case! 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): # Allow for different-length lists if (len(list1) == 0): return list2 elif (len(list2) == 0): # new base case! 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]
   
   
6. Check 9.2


7. Practical Programming with Recursion
   
   1. Recursive Debugging
      In the same way that we can sometimes write infinite while loops, we can sometimes write infinite recursive programs.
      
      Python usually catches this when the code repeats too many times. It then displays a RecursionError.
      
      def uhOh(n): if n == 0: return 0 else: return 1 + uhOh(n-1) print(uhOh(-10)) # RecursionError!
      
      Debugging recursive code with print statements 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.
      
      Note that we need to increase depth every time we call the function again- otherwise, it won't update. We'll make the depth parameter optional (giving it a starting value) so that it doesn't need to be included when the function is called.
      
      We can also make the function pause at a given depth by calling input(), then press enter when we're ready for it to continue. This helps when we need to debug programs on large inputs.
      
      def rangeSum(lo, hi, depth=0): print(" " * depth + "rangeSum(" + str(lo) + ", " + str(hi) + ")") if depth == 10: input("Pause (press enter to continue)") if (lo > hi): result = 0 else: result = lo + rangeSum(lo + 1, hi, depth + 1) print(" " * depth + "-->", result) return result print(rangeSum(10, 30))
   
   
   2. Wrapper Functions
      Sometimes we want to write a function that has one set of parameters, but we want a different set of parameters to be used in the recursive call.
      
      We can do this by writing a wrapper function around the core recursive function. The wrapper can set up the additional parameters and parse the recursive result to return the value that the user needs.
      
      The wrapper function itself is not recursive, but the function it calls is!
      
      # Problem: determine whether a given list has the same number of # positive numbers as negative numbers def isBalanced(lst): pos = countNums(lst, True) neg = countNums(lst, False) return pos == neg def countNums(lst, isPos): if len(lst) == 0: return 0 else: if lst[0] > 0 and isPos: return 1 + countNums(lst[1:], isPos) elif lst[0] < 0 and (not isPos): return 1 + countNums(lst[1:], isPos) else: return countNums(lst[1:], isPos) print(isBalanced([1, 4, 5, -3, -2, 4, -7, -9]))
   
   
   3. Expanding the Stack Size and Recursion Limit
      Python detects infinite recursion by keeping track of a 'stack' of function calls. When that stack hits a certain size limit (such as 1000 calls), Python decides that the function probably won't stop, and it throws an error. This can sometimes cause problems. If you run into this problem, try using the code below. You don't have to understand how it works for now.
      
      
      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 # But we know this isn't infinite recursion! It just needs more than 1000 function calls.
      
      
      2. The solution (on most platforms):
         def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) # Note: you do not need to understand the following code. You can just # copy and use it when needed. 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=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) # Note: you do not need to understand the following code. You can just # copy and use it when needed. 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=wrappedFn, args=[resultWrapper]) thread.start() thread.join() return resultWrapper[0] print(callWithLargeStack(rangeSum,1,123456)) # prints 7620753696
   
   
8. Check 9.3

---

Note: we'll go over all the following examples in class. You do not need to review them in advance unless you want to.

---

9. Multiple Recursive Calls
   The examples we've shown above could all have been solved using loops instead. So what's the point of recursion?
   
   Recursion is most powerful when we make multiple recursive calls in the recursive case, instead of just one. This lets us solve problems that we can't solve with loops.
   
   You can think of this approach as divide and conquer. In order to solve a problem, break it into multiple smaller parts, solve each of those, then combine the solutions to get the final answer.
   
   
   1. listSum
      # Technically we don't need multiple recursive calls here, but it's a nice simple example. # Sum the list by splitting it in half, then summing each half. 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
   
   
   2. fibonacci
      
      # The fibonacci sequence is a mathematical sequence where each element is equal to # the sum of the two elements that came before it. This translates nicely into recursive code! 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)])
   
   
   3. towersOfHanoi
      
      # Tower of Hanoi is a classic logic problem. Read more here: https://en.wikipedia.org/wiki/Tower_of_Hanoi def moveDiscs(pegs, startPeg, endPeg, tmpPeg, numDiscs): # If you have only one disc, just move it! if numDiscs == 1: # You can only move a disc to a peg that is empty, or to a disc larger than it. 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("Start peg state:", pegs) print("Number of discs moved:", towersOfHanoi(pegs)) print("End peg state:", pegs)
   
   
   4. mergeSort
      
      def merge(A, B): # beautiful, but impractical for large N 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 merge(A, B): # iterative (ugh) and destructive (double ugh), but practical... C = [ ] i = j = 0 while ((i < len(A)) or (j < len(B))): if ((j == len(B)) or ((i < len(A)) and (A[i] <= B[j]))): C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 return C def mergeSort(L): if (len(L) < 2): return L else: # No need for complicated loops- just merge sort each half, then merge! mid = len(L)//2 left = mergeSort(L[:mid]) right = mergeSort(L[mid:]) return merge(left, right) print(mergeSort([1,5,3,4,2,0]))
   
   
   5. quickSort
      
      # In Quick Sort, select an element to pivot around, organize all elements to # the left and right of the pivot, then Quick Sort each side. 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) print(quickSort([1,5,3,4,2,0]))
   
   
   6. floodFill
      Find the full code here: notes-recursion-floodFill.py
      Key excerpt:
      # To flood-fill a section of a grid in graphics, recursively flood-fill in all possible directions # We make the recursive call 'smaller' by first coloring the cell we're on, then checking for # already-colored cells at each call. def floodFill(data, row, col, depth=0): # Base case: going out of bounds, hitting a wall, or # reaching a cell that's already been colored. if ((row < 0) or (row >= data.rows) or (col < 0) or (col >= data.cols)): return # off-board! cell = data.cells[row][col] if (cell.isWall == True): return # hit a wall if (cell.depth >= 0): return # already been here # "fill" this cell cell.depth = depth cell.ordinal = len(data.floodFillOrder) data.floodFillOrder.append(cell) # then recursively fill its neighbors floodFill(data, row-1, col, depth+1) floodFill(data, row+1, col, depth+1) floodFill(data, row, col-1, depth+1) floodFill(data, row, col+1, depth+1)


10. Combining Iteration and Recursion
    In some problems, we'll need to combine iteration and recursion while problem solving. This often happens when the recursive program needs to produce an iterable result, like a list.
    
    
    1. powerset
       
       # Problem: given a list, a, produce a list containing all the possible subsets of a. def powerset(a): # Base case: the only possible subset of an empty list is the empty list. if (len(a) == 0): return [ [] ] else: # Recursive Case: remove the first element, then find all subsets of the remaining list. # Then duplicate each subset into two versions: one without the first element, and one with it. partialSubsets = powerset(a[1:]) allSubsets = [ ] for subset in partialSubsets: allSubsets.append(subset) allSubsets.append([a[0]] + subset) return allSubsets print(powerset([1,2,3]))
    
    
    2. permutations
       
       # Problem: given a list, a, find all possible permutations (orderings) of the elements of a def permutations(a): # Base Case: the only permutation of an empty list is the empty list if (len(a) == 0): return [ [] ] else: # Recursive Case: remove the first element, then find all possible permutations # of the remaining elements. For each permutation, insert a into every possible position. partialPermutations = permutations(a[1:]) allPerms = [ ] for subPermutation in partialPermutations: for i in range(len(subPermutation) + 1): allPerms.append(subPermutation[:i] + [ a[0] ] + subPermutation[i:]) return allPerms print(permutations([1,2,3]))
       
       
       # Alternative Approach: choose each element as the starting element of the permutation, # then find all possible permutations of the rest. def permutations(a): if (len(a) == 0): return [ [] ] else: allPerms = [ ] for i in range(len(a)): partialPermutations = permutations(a[:i] + a[i+1:]) for subPermutation in partialPermutations: allPerms.append([ a[i] ] + subPermutation) return allPerms print(permutations([1,2,3]))


11. Iteration vs. Recursion
    In most cases, we won't need to combine iteration and recursion; we'll just need to pick one. Here are a few examples of how problems can be solved iteratively or recursively.
    
    

    Function	Iterative Solution	Recursive Solution
    factorial	def factorial(n): result = 1 for i in range(2, n + 1): result *= i return result print(factorial(5))	def factorial(n): if (n < 2): return 1 else: return n * factorial(n - 1) 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"))
    digitSum	def digitSum(n): if n < 0: n = abs(n) result = 0 while n > 0: result += n % 10 n = n // 10 return result print(digitSum(-12345))	def digitSum(n): if (n < 0): return digitSum(abs(n)) elif (n < 10): return n else: return (n % 10) + digitSum(n // 10) print(digitSum(-12345))
    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

    
    In general, recursion and iteration have the following properties:
    
    

    	Recursion	Iteration
    Elegance
    Performance
    Debuggability

    
    Of course, these are just 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").


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