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!