C Program to Find the Sum of Natural Numbers Using Recursion

In this article, we will write a C program to find the sum of natural numbers with the help of recursion. The program takes a number N from the user as input, calculates the sum of natural numbers starting from 1 to N, and prints the result on the output screen.

Sample Example:

Input: N = 5
Output: Sum = 15
Explanation: Sum of 1 + 2 + 3 + 4 + 5 = 15

Input: N = 10
Output: Sum = 55
Explanation: Sum of 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

All positive integers starting from 1 to infinity are called natural numbers. There are various different ways to calculate the sum of N natural numbers. For example, you can directly use the formula N*(N + 1)/2 or you can use a for or while loop to add them all.

But in this article, we want to use recursion to find out the sum of the N natural numbers.

In computer programming, recursion is a concept where a function breaks down a large problem into smaller sub-problems by calling itself over again and again. The function call continues until we reach a non-breakable subproblem. This is known as a base case.

As we want to calculate the sum of N numbers, the base case will be when N = 1. This is because we can not break it further into smaller problems.

If N > 1, we will recursively call the function to get the sum of remaining (N – 1) natural numbers. This will continue until N becomes 1.

The following C program shows how you can find the sum of N natural numbers using recursion:

// C Program to Find the Sum of Natural Numbers using Recursion
#include <stdio.h>

int findSum(int N){
    // Base case: If N is 1, return 1
    if(N == 1){
        return 1;
    }
    
    // Recursive call to find sum of remaining N-1 numbers
    return N + findSum(N - 1);
}

int main() {
    
    int num, sum;

    printf("Enter a Number: ");
    scanf("%d", &num);
    
    // Get the sum of N natural numbers
    sum = findSum(num);
    
    // Print the result
    printf("The sum of %d Natural Numbers is: %d", num, sum);
    
    return 0;
}

Output:

Enter a Number: 20
The sum of 20 Natural Numbers is: 210

In this example, we have defined a recursive function findSum(). This function takes a number N as an argument and returns the sum of the first N natural numbers.

If the value of N is greater than 1, the findSum() function calls itself to get the sum of (N – 1) numbers. If N becomes 1, the base case is matched and it returns 1.

For example, if we pass N = 20, to get the sum of the first 20 natural numbers using the findSum() function, the first time findSum(20) will be called.

As the value of N > 1, therefore, findSum(19) will be called. On the next call, findSum(18) will be called. This will continue until N = 1.

Finally, 20 + 19 + 18 + …… + 2 + 1 is returned by the findSum() function which is the sum of the first 20 natural numbers. That’s how it works.

I hope you will find this article helpful. Thanks for reading!