Finding the sum of elements in an array is a common programming task forming the foundation of many advanced algorithms. In this article, we'll explore three approaches to solve this problem in C++: Recursion and Iteration.
Problem Statement
Given an array of integers calculate the sum of all its elements.
Examples
Example 1
Input: arr[] = {1, 2, 3}
Output: 6
Explanation: 1 + 2 + 3 = 6
Example 2
Input: arr[] = {15, 12, 13, 10}
Output: 50
Explanation: 15 + 12 + 13 + 10 = 50
Approaches to Solve the Problem
1. Using Recursion
The recursive approach breaks the problem into smaller subproblems by summing the first element with result of recursively summing the rest of the array.
Implementation
#include <iostream>
using namespace std;
// Recursive function to calculate the sum
int sum(int arr[], int n) {
// Base case: if the array size is 0
if (n == 0) {
return 0;
}
// Recursive case: add the first element to sum of the remaining array
return arr[0] + sum(arr + 1, n - 1);
}
int main() {
int arr[] = {12, 3, 4, 15};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of the array is: " << sum(arr, n) << endl;
return 0;
}
Output
Sum of the array is: 34
Complexity Analysis
Time Complexity: O(n) – One recursive call per array element.
Auxiliary Space: O(n) – Space used by the recursion stack.
2. Using Iteration
An iterative approach uses a loop to calculate the sum by adding each element to a running total.
Implementation
#include <iostream>
using namespace std;
// Iterative function to calculate the sum
int sum(int arr[], int n) {
int total = 0; // Initialize sum to 0
// Loop through the array and add each element
for (int i = 0; i < n; i++) {
total += arr[i];
}
return total;
}
int main() {
int arr[] = {12, 3, 4, 15};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of the array is: " << sum(arr, n) << endl;
return 0;
}
Output
Sum of the array is: 34
Complexity Analysis
Time Complexity: O(n) – One iteration over all elements.
Auxiliary Space: O(1) – No extra space is used.
0 Comments