name: inverse layout: true class: taylor msoe --- class: center, middle .title[ # Recursion ## Defining a problem in terms of itself ] ??? * **P** speaker view * **C** clone slideshow * **?** help --- # Recurision - In Theory * A recursive method exhibits the following two characteristics: -- * A trivial base case (or cases) -- - A problem so small, that it is trivial to determine the answer -- * A recursive step -- - A set of rules that reduces all successive cases toward the base case --- # Recurision - In Practice * Process of defining a problem in terms of a simplier version of itself -- * Forces us to approach solving a problem in a different way -- * Identify a sub-problem -- - This is typically the hard part -- * Solve whole problem assuming we know the solution to the sub-problem -- - (recursive step) -- * Determine when the sub-problem is so small it is trivial to solve -- - (base case) --- # Non-Recursion: Sum of `List` * Iterate through list and add elements to an accumulator ``` public static Integer sum(List
list) { Integer sum = 0; for(Integer val : list) { sum += val; } return sum; } ``` --- # Recursion: Sum of elements in `List` * Identify a sub-problem -- - Smaller list - sublist with all but first element -- * Recursive step: add value of first element to sum of the sublist -- ``` return list.get(0) + sum(list.sublist(1, list.size())); ``` -- * Base case: List with no elements - sum = 0 --- # Recursion: Sum of elements in `List` ``` public static Integer sum(List
list) { return list.isEmpty() ? 0 // Base case : list.get(0) + sum(list.sublist(1, list.size())); // Recursive step } ``` --- # Example: $x^y$ * Identify a sub-problem -- - $x^{y-1}$ -- * Recursive step -- - $x \times x^{y-1}$ -- * Base case -- - $x^{0} = 1$ --- # Recursive Backtracking with List * Identify a sub-problem -- - Sublist with all but first element -- * Recursive step -- - Is problem solved by the sub-problem? -- - Is problem solved with first element combined with sub-problem solution? -- * Base case -- - Empty list --- # Example: Group Sum Given a list, can a subset of the list values sum to a `target` value? `groupSum(List
list, int target)` -- * Identify the sub-problem -- - `list.sublist(1, list.size())` -- * Recursive step -- - `groupSum(list.sublist(1, list.size()), target)` -- - `groupSum(list.sublist(1, list.size()), target - list.get(0))` -- * Base case -- - `target == 0` for empty list --- # Group Sum Given a list, can a subset of the list values sum to a `target` value? ``` public static boolean groupSum(List
list, int target) { return list.isEmpty() ? target == 0 : // Group sum when first element is ignored groupSum(list.sublist(1, list.size()), target) || // Group sum when first element is used groupSum(list.sublist(1, list.size()), target - list.get(0)); } ```