Here is a C program to find the sum of elements of array using recursion. We will first take N numbers as input from user using scanf function and store it in an integer array. Now, we have to find sum of all elements of array from index 0 to N-1 using recursion.
For Example
Input Array : 1 2 3 4 5Sum of Array Element : 15
Algorithm to find sum of all array elements using recursion
- Initialize lastIndex with the index of last element in array(lastIndex = N-1).
- We can calculate the sum of inputArray elements form index 0 to N-1 by adding sum of elements form 0 to N-2 and inputarray[N-1].
- Let getSum(inputArray, lastIndex) function calculates sum of all elements of inputArray from index 0 to lastIndex.
- inputArray[0] + inputArray[1] ... inputArray[lastIndex-1] + inputArray[lastIndex] = (inputArray[0] + inputArray[1] ... inputArray[lastIndex-1]) + inputArray[lastIndex]
- getSum(inputArray, N-1) = getSum(inputArray, lastIndex-1) + inputArray[lastIndex]./li>
- Recursion will terminate when lastIndex < 0.
C program to find sum of array elements using recursion
Below program, contains a user defined function getSum(int *inputArray, int lastIndex), which takes a pointer to an integer array and lastIndex as input and returns the sum of all elements of inputArray from index 0 to lastIndex. Function getSum calls itself recursively to calculate the sum of array form index 0 to lastIndex-1.
For Example, Let inputArray contains 5 elements from index 0 to 4
To find the sum of all elements we will call getSum function as getSum(inputArray, 4). Function getSum internally calls itself as getSum(inputArray, 3) to find sum of elements from index 0 to 3, and then it adds inputArray[4] to the result of getSum(inputArray, 3) and return.
#include <stdio.h>
int getSum(int *inputArray, int lastIndex);
int main(){
int inputArray[100], counter, numberCount;
printf("Enter number of elements in Array: ");
scanf("%d", &numberCount);
printf("Enter %d numbers \n ", numberCount);
for(counter = 0; counter < numberCount; counter++){
scanf("%d", &inputArray[counter]);
}
printf("Sum of all numbers are : %d",
getSum(inputArray,numberCount - 1));
return 0;
}
int getSum(int *inputArray, int lastIndex){
int mid;
if(NULL == inputArray || lastIndex < 0)
return 0;
return inputArray[lastIndex] + getSum(inputArray, lastIndex -1);
}
Output
Enter number of elements in Array: 6 Enter 6 numbers 1 3 5 2 7 4 Sum of all numbers are : 22
C program to calculate sum of an array using divide and conquer.
Algorithm to calculate sum of array using divide and conquer- Divides the inputArray into two equal half.
- Find the sum of elements of left and right half of the array recursively.
- Add the sum of both half of array to get the sum of whole array.
- getSum(inputArray, 0, N-1) = getSum(inputArray, 0, mid) + getSum(inputArray, mid+1, N-1); where mid = (N-1)/2;
- Recursion will terminate when size of the array becomes less than 1.
Below program uses a user defined function getSum. It calculates the sum of an array by splitting it into two sub-array and calculating the sum of each sub-array recursively. Finally it adds the sum of both sub-arrays to get the sum of original array.
For Example, Let inputArray contains eight elements from index 0 to 7
To find the sum of all elements we will call getSum function as getSum(inputArray, 0, 7). Function getSum internally calculates the mid index of the array as (0+7)/2 = 3 and calls itself recursively as getSum(inputArray, 0, 3) to find sum of elements from index 0 to 3(left half of array), and getSum(inputArray, 4, 7) to find sum of elements from index 4 to 7(right half of array). Then it returns the sum of whole array by adding the sum of left and right half of the array.
#include <stdio.h>
int main(){
int inputArray[100], counter, numberCount;
printf("Enter number of elements in Array: ");
scanf("%d", &numberCount);
printf("Enter %d numbers \n ", numberCount);
for(counter = 0; counter < numberCount; counter++){
scanf("%d", &inputArray[counter]);
}
printf("Sum of all numbers are : %d",
getSum(inputArray, 0 ,numberCount - 1));
return 0;
}
int getSum(int *inputArray, int leftIndex, int rightIndex){
int mid;
if(NULL == inputArray || leftIndex > rightIndex)
return 0;
if(leftIndex == rightIndex)
return inputArray[leftIndex];
mid = (leftIndex + rightIndex) / 2;
return getSum(inputArray, leftIndex, mid) +
getSum(inputArray, mid+1, rightIndex);
}
Output
Enter number of elements in Array: 8 Enter 8 numbers 1 3 5 7 9 2 4 6 Sum of all numbers are : 37
Related Topics