- Write 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 5
Sum of Array Element : 15
Algorithm to find sum of all array elements using recursion
Let inputArray is an integer array containing N elements from index 0 to N-1 and lastIndex is an integer variable.
- 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.
/* * C Program to find sum of N numbers using recursion */ #include <stdio.h> #include <conio.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)); getch(); return 0; } /* * getSum(array, index) = array[index] + getSum(array, index-1); */ int getSum(int *inputArray, int lastIndex){ int mid; if(NULL == inputArray || lastIndex < 0) return 0; return inputArray[lastIndex] + getSum(inputArray, lastIndex -1); }
Program 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
Let inputArray is an integer array of length N.
- 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.
/* * C Program to find sum of N numbers using divide and conquer */ #include <stdio.h> #include <conio.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)); getch(); return 0; } /* * getSum function divides the input array into two equal half * and tries to find the sum of elements in both half recursively. * Finally, it adds the sum of left and right sub Array and return. * @Algorithm Divide and Conquer */ 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); }
Program 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