Problem Statement

Given an array A[], we need to find the sum of its elements using Tail Recursion Method.

We generally want to achieve tail recursion (a recursive function where recursive call is the last thing that function does) so that compilers can optimize the code. Basically, if recursive call is the last statement, the compiler does not need to save the state of parent call. 

Examples

Example 1:

Input: arr = {1, 5, 7}

Output: 13

Theory

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

1. Base Case: If the array is empty, return 0.
2. Recursive Step: Add the first element of the array to the sum of the rest of the array elements.
3. Tail Recursion: Use tail recursion to optimize the space complexity.

Approach

Code Implementation in C++:

#include <iostream>
using namespace std;

// Tail recursive function to calculate the sum of array elements
int arrSum(int array[], int size, int sum = 0) {
    // Base Case: if size is 0, return sum
    if (size == 0) 
        return sum;

    // Tail recursive step: add the current element to sum and call the function with updated size and sum
    return arrSum(array, size - 1, sum + array[size - 1]);
}

int main() {
    int array[] = {2, 55, 1, 7};
    int size = sizeof(array) / sizeof(array[0]);
    
    // Call the arrSum function
    cout << "Sum of array elements: " << arrSum(array, size) << endl;

    return 0;
}

Complexity Analysis

• Time Complexity:O(n)
  • Since each element of the array is visited once.
• Space Complexity:O(1)
  • Since tail recursion is used, the space complexity is optimized.