# CMU 15-112: Fundamentals of Programming and Computer Science Class Notes: 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 + 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, list2}, 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".