Problem Statement

Calculate the sum of elements in an array using the recursion.

Examples

Example 1:

Input: arr = {1, 2, 3, 4, 5}
Output: 15

Explanation: 1+2+3+4+5 = 15

Different Ways

1️⃣ First Way

Theory

To calculate the sum of elements in an array using recursion, we can follow these steps:

• Base Case: If n (the size of the array) is less than or equal to 0, return 0.
• Recursive Step: Recursively calculate the sum of the elements in the array except the last one.
• Addition: Add the last element to the sum obtained from the recursive call.

Code Implementation in C++:

#include <iostream>
using namespace std;

// Function to calculate the sum of array elements using recursion
int arraySum(int arr[], int n) {
    // Base case: if n is less than or equal to 0, return 0
    if (n <= 0)
        return 0;
    // Recursive step:
    // Return the sum of the last element and the sum of the rest of the array
    return arr[n - 1] + arraySum(arr, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Call the arraySum function to get the sum of array elements
    int sum = arraySum(arr, n);
    
    // Print the sum of array elements
    cout << "Sum of array elements: " << sum << endl;

    return 0;
}

Output:

Sum of array elements: 15

Complexity Analysis:

• Time Complexity:O(n)
  • Since each element of the array is visited once.
• Space Complexity:O(n)
  • Due to the recursion stack, which can go as deep as the number of element in the array.

2️⃣ Way 2

Intuition:

Computing the sum of an array's elements through recursion involves thinking about adding the first element to the sum of the rest. This process continues by recursively considering one element at a time, gradually reducing the array until reaching the point where no elements are left to add.

Approach:

1. Define a recursive helper function sum(nums, left) where nums is the array and left is the current index.
2. In the helper function: Base case: If the left index is out of bounds (i.e., left >= nums.length), return 0 because there are no more elements to add. Recursive case: Add the current element nums[left] to the sum of the remaining elements, obtained by recursively calling the function with the next index left + 1.
3. The initial call to the helper function is made from the main function with the starting index 0.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int arraySum(vector<int>& nums) {
        // Start from index 0
        return sum(nums, 0);
    }

private:
    int sum(vector<int>& nums, int left) {
        // Base case: out of bounds
        if (left >= nums.size()) {
            return 0;
        }
        // Add current element and recurse
        return nums[left] + sum(nums, left + 1);
    }
};

// Main method for testing
int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3};   
    int result = solution.arraySum(nums); 
    cout << result << endl;     
    return 0;
}

Complexity Analysis:

• Time Complexity : O(N) The time complexity is O(N) because each element in the array is processed exactly once.
• Space Complexity : O(N)The space complexity is O(N) due to the recursion stack, which can grow up to the size of the array.

3️⃣ Tail Recursion

In tail recursion, the recursive call is the last operation in the function, which helps optimize memory usage as the previous function frames can be discarded.

Code:

#include <iostream>
using namespace std;

// Tail recursive function to find the sum of array elements
int sumArray(int arr[], int n, int accumulator = 0) {
    // Base case: if the array is empty
    if (n == 0)
        return accumulator;
    
    // Tail recursion: add the current element to accumulator and recurse
    return sumArray(arr, n - 1, accumulator + arr[n - 1]);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Call the tail recursive function
    int sum = sumArray(arr, n);
    
    cout << "Sum of array elements: " << sum << endl;

    return 0;
}

Explanation:

• sumArray function: It takes three parameters — the array arr, its size n, and an accumulator (default initialized to 0).
• The function checks the base case: if n == 0, it returns the accumulated sum.
• Otherwise, it adds the current element (arr[n - 1]) to the accumulator and makes the recursive call with n - 1.