Coding Exercise: Array Sum Using Recursion

Write recursive function to sum all elements in array: [1,2,3,4] → 10.

Two approaches: index-based and pointer-based.

Problem Statement

Input: Array arr, size n

Output: Sum of all elements

Examples: [1,2,3] → 6, [5] → 5, [] → 0

Approach 1: Index-Based (Recommended)

sum(arr, n) = arr[0] + sum(arr+1, n-1)

#include <iostream>
using namespace std;

int arraySum(int arr[], int n) {
    // Base case: empty array
    if (n <= 0) return 0;
    
    // Recursive case
    return arr[0] + arraySum(arr+1, n-1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    cout << "Sum = " << arraySum(arr, n) << endl;
    return 0;
}

Approach 2: Index Parameter

int arraySum(int arr[], int n, int index = 0) {
    if (index >= n) return 0;
    return arr[index] + arraySum(arr, n, index+1);
}

Dry Run: [3, 1, 4, 1, 5], n=5

arraySum([3,1,4,1,5], 5)
→ 3 + arraySum([1,4,1,5], 4)
→ 3 + 1 + arraySum([4,1,5], 3)
→ 3 + 1 + 4 + arraySum([1,5], 2)
→ 3 + 1 + 4 + 1 + arraySum([5], 1)
→ 3 + 1 + 4 + 1 + 5 + arraySum([], 0)
→ 3+1+4+1+5+0 = 14 ✓

Test Cases

[1,2,3] → 6
[5] → 5
[] → 0
[-1,1] → 0
[10,20,30] → 60

Complexity Analysis

Time: O(n) - visit each element once

Space: O(n) - recursion stack depth

Practice Variations

1. Find maximum element recursively

2. Count occurrences of target value

3. Array rotation using recursion

Conclusion

Mastered array recursion! Array+1 technique is powerful.

Next: Binary search or merge sort recursively.