C Program to Find Sum of Array Using Recursion

You can find the sum of an array using recursion in C by defining a function like int sumArray(int arr[], int n) that returns 0 when n == 0 and otherwise returns arr[n-1] + sumArray(arr, n-1).

Examples

Inputarr = {5}, n = 1

Output5

Inputarr = {1, 2, 3, 4, 5}, n = 5

Output15

Inputarr = {}, n = 0

Output0

How to Think About It

To find the sum of an array using recursion, think of the array as a list where you add the last element to the sum of all previous elements. The base case is when the array size is zero, then the sum is zero. Otherwise, add the last element to the sum of the rest.

Algorithm

1

Check if the size of the array is zero; if yes, return 0.

2

Otherwise, return the last element plus the sum of the array excluding the last element.

3

Repeat this until the base case is reached.

Code

c

#include <stdio.h>

int sumArray(int arr[], int n) {
    if (n == 0) {
        return 0;
    }
    return arr[n - 1] + sumArray(arr, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = sumArray(arr, n);
    printf("Sum of array elements: %d\n", sum);
    return 0;
}

Output

Sum of array elements: 15

Dry Run

Let's trace the array {1, 2, 3, 4, 5} through the recursive sumArray function.

1

Initial call

sumArray(arr, 5) calls sumArray(arr, 4) and adds arr[4] = 5

2

Second call

sumArray(arr, 4) calls sumArray(arr, 3) and adds arr[3] = 4

3

Third call

sumArray(arr, 3) calls sumArray(arr, 2) and adds arr[2] = 3

4

Fourth call

sumArray(arr, 2) calls sumArray(arr, 1) and adds arr[1] = 2

5

Fifth call

sumArray(arr, 1) calls sumArray(arr, 0) and adds arr[0] = 1

6

Base case

sumArray(arr, 0) returns 0

7

Return values

Returns 0 + 1 = 1, then 1 + 2 = 3, then 3 + 3 = 6, then 6 + 4 = 10, then 10 + 5 = 15

Function Call	Returned Value
sumArray(arr, 0)	0
sumArray(arr, 1)	1
sumArray(arr, 2)	3
sumArray(arr, 3)	6
sumArray(arr, 4)	10
sumArray(arr, 5)	15

Why This Works

Step 1: Base Case

The function returns 0 when the array size is 0, stopping the recursion.

Step 2: Recursive Call

Each call adds the last element of the current array segment to the sum of the rest.

Step 3: Summation

The recursive calls build up the total sum by adding elements from the end to the start.

Alternative Approaches

Iterative approach

c

#include <stdio.h>

int sumArrayIterative(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Sum of array elements: %d\n", sumArrayIterative(arr, n));
    return 0;
}

This uses a loop instead of recursion, which is often more efficient and avoids stack overhead.

Tail recursion

c

#include <stdio.h>

int sumArrayTail(int arr[], int n, int acc) {
    if (n == 0) return acc;
    return sumArrayTail(arr, n - 1, acc + arr[n - 1]);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Sum of array elements: %d\n", sumArrayTail(arr, n, 0));
    return 0;
}

Tail recursion can be optimized by some compilers to avoid extra stack usage.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself once per element, so it runs in linear time proportional to the array size.

Space Complexity

Each recursive call adds a new layer to the call stack, so space used is proportional to the array size.

Which Approach is Fastest?

The iterative approach is fastest and uses constant space, while recursion is easier to write but uses more memory.

Approach	Time	Space	Best For
Recursive	O(n)	O(n)	Simple code, learning recursion
Iterative	O(n)	O(1)	Performance and memory efficiency
Tail Recursion	O(n)	O(1) if optimized	Recursion with better memory use