Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explained how to get the sum of N natural numbers using recursion and implement the technique in C Programming Language.
Table of contents
- Problem statement
- Approach to solve
- Implementation
- Output
Problem statement
In this problem, we have to find the sum of n natural numbers using recursion.
- First we create a function dis()
- Under that function we check if n is less than or equal to 1. If this statement is true then we return the value of n
- Else we return the value of n+dis(n-1).
- dis(n-1) is the sum of all natural numbers from n-1 till 1.
- Now under the main function we take input of the value of n and then print the function dis(n).
- dis(n) stores the value of summation of n natural numbers
Implementation
Following is the implemention of the code in C programming language:
#include<stdio.h>
int dis(int n)
{
if(n<=1)
return n;
return n+dis(n-1);
}
int main()
{
int n;
printf("enter the value of n=");
scanf("%d",&n);
printf("sum=%d",dis(n));
return 0;
}
Output
Run the code as follows:
gcc code.c
./a.out
Following is the output of the program:
Enter the value of n=6
sum=21
Time and Space Complexity
The Time Complexity of this technique is O(N) as we are traversing through all N natural numbers one by one and adding them in recursion.
The Space Complexity is O(N) as well.
This is because there will be N recursive calls. One call for each natural number. If we implement the iterative version of this technique, the space complexity will be O(1).
Additionally, the sum of first N natural numbers can be calculated using a direct formula and hence, resulting in constant time O(1).
Sum of N natural numbers = N * (N+1) / 2
So, if N=6, sum = 6 * 7/2 = 21.
With this article at OpenGenus, you must have the complete idea of how to get the sum of N natural numbers using recursion.