Array Sum

Write a recursive function sum_array(arr) that returns the sum of all elements in an array. Input: [1, 2, 3, 4, 5] → Output: 15. Input: [] → Output: 0. No for or while loops allowed.

The recursive insight: $\text{sum}([a_0, a_1, \ldots, a_{N-1}]) = a_0 + \text{sum}([a_1, \ldots, a_{N-1}])$. The base case is an empty array with sum 0. This "peel off the first element" pattern is fundamental to recursive array processing.

1. Base case: if len(arr) == 0, return 0.
2. Recursive case: return arr[0] + sum_of_array(arr[1:]).
3. arr[1:] creates a new sub-array, shrinking the problem by one element each call.

• Forgetting the base case for an empty array, leading to infinite recursion
• Using arr[0] without checking if the array is empty first (IndexError)
• Not realizing arr[1:] costs $O(N)$ per call — hidden total cost is $O(N^2)$
• For production code, Python's built-in sum() is more efficient

This problem teaches recursive decomposition: process the head, recurse on the tail. While $O(N^2)$ slicing makes it impractical for real use, it builds the recursive thinking needed for merge sort, tree traversals, and divide-and-conquer.