Search anything:

Sum of N natural numbers using recursion

Learn Algorithms and become a National Programmer
Indian Technical Authorship Contest starts on 1st July 2023. Stay tuned.

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


Following is the implemention of the code in C programming language:

int dis(int n)
	return n;
	return n+dis(n-1);
int main()
	int n;
	printf("enter the value of n=");
	return 0;


Run the code as follows:

gcc code.c

Following is the output of the program:

Enter the value of n=6

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.