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.