- 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 5Sum 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

**Related Topics**