Sum of N natural numbers using recursion

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

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.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.