×

Search anything:

# Sum of N natural numbers using recursion

#### C Programming recursion

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.

• 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

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.

Sum of N natural numbers using recursion