C Program to Find Sum of Array Elements using Recursion

C Program to Find Sum of Array Elements using Recursion

by
  • 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 Array Elements using Recursion

/*
* 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 calculate sum of an array using divide and conquer

/*
* 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