Recursion on Arrays

Part of: Recursion

Processing Arrays Recursively Unlike strings, we usually do not create smaller arrays (that is wasteful). Instead we pass an index that marks where the current sub-problem begins. The array stays the same; the index shrinks the problem. The pattern: a helper takes the array plus an index i. The base case is when i reaches arr.length (nothing left). Otherwise, combine arr[i] with the recursive result for i + 1. Summing an Array Call it with sum(arr, 0). Trace {4, 2, 7}: - sum(arr,0) = 4 + sum(arr,1) - sum(arr,1) = 2 + sum(arr,2) - sum(arr,2) = 7 + sum(arr,3) - sum(arr,3) = 0 (base case) - Up: 7+0=7, 2+7=9, 4+9=13 Finding a Maximum The same index trick finds the largest element: Note: Math.max is a convenience method that is not on the AP Java Quick Reference. On the exam you would keep the larger of the two values with an if statement instead. Wrapper Methods Users should not have to pass a starting index. A common technique is a wrapper (public) method that calls the recursive helper with index 0: This keeps the public interface clean while the helper does the recursion. Key Idea Index-based recursion avoids copying data: the array is shared, and only the integer index moves forwar

Challenge: Recursive Array Sum