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

1. Multiple Recursive Calls
   1. listSum
   2. fibonacci
   3. towersOfHanoi
   4. mergeSort
   5. quickSort
2. Combining Iteration and Recursion
   1. powerset
   2. permutations
3. Iteration vs. Recursion
   1. factorial
   2. reverse
   3. digitSum
   4. gcd

1. Multiple Recursive Calls
   Recursion is perhaps most powerful when we make multiple recursive calls in the recursive case. This often lets us solve problems that we cannot easily solve with loops. You can think of this approach as divide and conquer. In order to solve a problem, we break it into 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. package main import "fmt" func listSum(L []int) int { if len(L) == 0 { return 0 } else if (len(L) == 1) { return L[0] } else { mid := len(L) / 2 return listSum(L[:mid]) + listSum(L[mid:]) } } func main() { fmt.Println(listSum([]int{2,3,5,7,11})) // 28 }
   
   
   2. fibonacci
      
      // In the Fibonacci sequence, each element is the sum of the two // elements before it. This translates nicely into recursive code! package main import "fmt" func fib(n int) int { if (n < 2) { return 1 } else { return fib(n-1) + fib(n-2) } } func main() { fibs := make([]int, 0) for i := 0; i < 15; i ++ { fibs = append(fibs, fib(i)) } fmt.Println(fibs) }
   
   
   3. towersOfHanoi
      
      • First attempt (without Go)
        // 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)
      • Turn into Go (the "magic" is recursion!)
        func move(n, source, target, temp int) { move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) } func main() { move(2, 0, 1, 2) // Does not work -- infinite recursion }
      • Once again, with a base case
        package main import "fmt" func move(n, source, target, temp int) { if n == 1 { fmt.Print("(", source, ",", target, ")") } else { move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) } } func main() { move(2, 0, 1, 2) }
      • Finally, with a nice wrapper
        package main import "fmt" func move(n, source, target, temp int) { if n == 1 { fmt.Print("(", source, ",", target, ")") } else { move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) } } func hanoi(n int) { fmt.Println("Solving Towers of Hanoi with n =", n) move(n, 0, 1, 2) fmt.Println() } func main() { hanoi(4) }
   
   
   4. mergeSort
      
      // Recursive merge func merge(A, B []int) { // beautiful, but impractical for large N if (len(A) == 0 || len(B) == 0) { return append(A, B...) } else { if A[0] < B[0] { return append([]int{A[0]}, merge(A[1:], B)...) } else { return append([]int{B[0]}, merge(A, B[1:])...) } } }
      package main import "fmt" func merge(A, B []int) []int { C := []int{} i := 0 j := 0 for (i < len(A) || j < len(B)) { if (j == len(B) || (i < len(A) && A[i] <= B[j])) { C = append(C, A[i]) i += 1 } else { C = append(C, B[j]) j += 1 } } return C } func mergeSort(L []int) []int { if len(L) < 2 { return L } else { mid := len(L) / 2 left := mergeSort(L[:mid]) right := mergeSort(L[mid:]) return merge(left, right) } } func main() { fmt.Println(mergeSort([]int{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. package main import "fmt" func quickSort(L []int) []int { if len(L) < 2 { return L } else { first := L[0] rest := L[1:] lo := []int{} hi := []int{} for _, v := range rest {if v < first {lo = append(lo, v)}} for _, v := range rest {if v >= first {hi = append(hi, v)}} return append(quickSort(lo), append([]int{first}, quickSort(hi)...)...) } } func main() { fmt.Println(quickSort([]int{1,5,3,4,2,0})) }


2. Combining Iteration and Recursion
   We sometimes need to combine iteration and recursion while problem solving.
   
   
   1. powerset
      
      // Problem: given a list a, return a list with all the possible subsets of a. package main import "fmt" func powerset(a []int) [][]int { // Base case: the only possible subset of an empty list is the empty list. if len(a) == 0 { return [][]int{[]int{}} } else { // Recursive Case: remove the first element, then find all subsets of the // remaining list. Then for each subset, use two versions of that subset: // one without the first element, and another one with it. partialSubsets := powerset(a[1:]) allSubsets := [][]int{} for _, subset := range partialSubsets { allSubsets = append(allSubsets, subset) allSubsets = append(allSubsets, (append([]int{a[0]}, subset...))) } return allSubsets } } func main() { fmt.Println(powerset([]int{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 in that permutation. partialPermutations = permutations(a[1:]) allPerms = [ ] for perm in partialPermutations: for i in range(len(perm) + 1): allPerms.append(perm[:i] + [ a[0] ] + perm[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 perm in partialPermutations: allPerms.append([ a[i] ] + perm) return allPerms print(permutations([1,2,3]))


3. Iteration vs. Recursion
   

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