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

1. Predict
2. General Recursive Form
3. Basic Examples
   1. listSum
   2. rangeSum
   3. power
4. Multiple Base/Recursive Cases
   1. power
   2. interleave
5. Practical Programming with Recursion
   1. Infinite Recursion and Stack Overflow
   2. Recursive Debugging
   3. Wrapper Functions
6. Popular Recursion

1. Predict
   
   package main import "fmt" func f(n int) string { if n == 0 { return "boo!" } else { fmt.Println(n) return f(n-1) } } func main() { fmt.Println(f(5)) }


2. General Recursive Form
   Recursion technically means that some function calls itself. However, fundamentally, using recursion is more than that -- it is a powerful way to think about problem solving.
   
   In recursion, we divide a function into two possible cases: a base case, which returns the result for a known small value, and a recursive case, which computes a result by calling the same function on a smaller value. In other words: we solve the problem by assuming it's already solved!
   
   
   func recursiveFunction() { if (this is the base case) { do something non-recursive } else { do something recursive } }


3. Basic Examples
   We could write these with loops, but it's useful to practice basic recursion this way:
   
   
   1. listSum
      package main import "fmt" // Problem: sum all the numbers in a given list func listSum(L []int) int { // 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:]) } } func main() { fmt.Println(listSum([]int{2,3,5,7,11})) // 28 }
   
   
   2. rangeSum
      package main import "fmt" // Problem: sum all of the numbers from lo to hi, inclusive func rangeSum(lo, hi int) int { if (lo > hi) { return 0 } else { return lo + rangeSum(lo + 1, hi) } } func main() { fmt.Println(rangeSum(10,15)) // 75 }
   
   
   3. power
      package main import "fmt" // Problem: raise the number base to the given exponent func power(base, expt int) int { // assume expt is a non-negative integer if (expt == 0) { return 1 } else { return base * power(base, expt-1) } } func main() { fmt.Println(power(2, 5)) // 32 }


4. Multiple Base/Recursive Cases
   Sometimes, we need to include more than one base or recursive case when solving a problem.
   1. power
      package main import "fmt" func power(base, expt float64) float64 { // This version allows for negative exponents if expt == 0 { return 1.0 } else if (expt < 0) { return 1.0 / power(base, -expt) } else { return base * power(base, expt-1) } } func main() { fmt.Println(power(2, 5)) // 32 fmt.Println(power(2, -5)) // 1 / 32 = 0.03125 }
   
   
   2. interleave
      package main import "fmt" func interleave(list1, list2 []int) []int { // Allow for different-length lists if (len(list1) == 0) { return list2 } else if (len(list2) == 0) { return list1 } else { return append([]int{list1[0], list2[0]}, interleave(list1[1:], list2[1:])...) } } func main() { fmt.Println(interleave([]int{1,2}, []int{3,4,5,6})) // [1 3 2 4 5 6] }


5. Practical Programming with Recursion
   
   1. Infinite Recursion and Stack Overflow
      Just as we can write infinite loops, we can also write infinite recursive functions, which result in stack overflow, producing a RecursionError.
      
      package main import "fmt" func sumToN(n int) int { if n == 0 { return 0 } else { return n + sumToN(n - 1) } } func main() { fmt.Println(sumToN(3)) // 6 works! fmt.Println(sumToN(-3)) // fatal error: stack overflow }
      
      
   2. Recursive Debugging
      Debugging recursive code can be tricky because we not only have to know which function we are in, but which specific call to that function (since it calls itself repeatedly)! We can make it easier by keeping track of the recursion depth using an optional parameter, then adjusting the output based on that depth.
      
      package main import ( "fmt" "strings" ) func rangeSum(lo, hi, depth int) int { fmt.Println(strings.Repeat(" ", depth), "rangeSum(", lo, ",", hi, ")") var result int if depth == 10 { // Try this to pause execution in VSCode (like Python's input) // fmt.Scanln() } if (lo > hi) { result = 0 } else { result = lo + rangeSum(lo + 1, hi, depth + 1) } fmt.Println(strings.Repeat(" ", depth), "-->", result) return result } func main() { fmt.Println(rangeSum(10, 30, 0)) }
   
   
   3. Wrapper Functions
      Sometimes we want to write a function with certain parameters, but it would be helpful to use different parameters 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 on the way in, and it can also parse and perhaps modify the recursive result on the way out. The wrapper function itself is not recursive, but the function it calls is!
      
      package main import "fmt" func rangeSumHelper(lo, hi, sumSoFar int) int { if (lo > hi) { return sumSoFar } else { return rangeSumHelper(lo + 1, hi, lo + sumSoFar) } } func rangeSum(lo, hi int) int { return rangeSumHelper(lo, hi, 0) } func main() { fmt.Println(rangeSum(10, 15)) // 75 }


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