Get this book -> Problems on Array: For Interviews and Competitive Programming

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.