Recursion is a process in which a function calls itself directly or indirectly. Recursive algorithms are widely used in computer science to solve complex problems by breaking them down into simpler ones.

You can better understand recursive concepts by solving basic programming problems like the “product of two numbers”, “the sum of first n natural numbers”, and more.

In this article, you’ll learn how to find the sum of the first n natural numbers using recursion.

## Problem Statement

You’re given a natural number **n**, you need to find the sum of the first **n** natural numbers using recursion.

**Example 1**: Let n = 5

Therefore, the sum of the first 5 natural numbers = 1 + 2 + 3 + 4 + 5 = 15.

Thus, the output is 15.

**Example 2**: Let n = 7

Therefore, the sum of the first 7 natural numbers = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Thus, the output is 28.

**Example 3**: Let n = 6

Therefore, the sum of the first 6 natural numbers = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Thus, the output is 21.

## Recursive Function to Find the Sum of First N Natural Numbers

Most recursive functions have the following relative structure:

`FUNCTION name`

IF condition THEN

RETURN result

ELSE

CALL FUNCTION name

END FUNCTION

To find the sum of the first n natural numbers, observe and apply the following pseudocode:

`findSum(n):`

IF n<=1 THEN

RETURN n

ELSE

RETURN n + findSum(n-1)

END FUNCTION

Now, you can implement this pseudocode in your favorite programming language.

**Note**: You can also find the sum of the first n natural numbers using the following mathematical formula:

Sum of n natural numbers = n * (n + 1) / 2

Using this method you can find the sum in one step without using recursion.

## C++ Implementation to Find the Sum of First N Natural Numbers Using Recursion

Below is the C++ implementation to find the sum of the first n natural numbers using recursion:

`// C++ implementation to find the sum of`

// first n natural numbers using recursion

#include <iostream>

using namespace std;

// Recursive function to find the sum of first n natural numbers

int findSum(int n)

{

if (n<=1)

{

return n;

}

else

{

return n + findSum(n-1);

}

}

// Driver code

int main()

{

int n1 = 5, n2 = 7, n3 = 6;

cout << "n1: " << n1 << endl;

cout << "n2: " << n2 << endl;

cout << "n3: " << n3 << endl;

cout << "Sum of first " << n1 << " natural numbers: " << findSum(n1) << endl;

cout << "Sum of first " << n2 << " natural numbers: " << findSum(n2) << endl;

cout << "Sum of first " << n3 << " natural numbers: " << findSum(n3) << endl;

return 0;

}

Output:

`n1: 5 `

n2: 7

n3: 6

Sum of first 5 natural numbers: 15

Sum of first 7 natural numbers: 28

Sum of first 6 natural numbers: 21

## Python Implementation to Find the Sum of First N Natural Numbers Using Recursion

Below is the Python implementation to find the sum of the first n natural numbers using recursion:

`# Python implementation to find the sum of`

# first n natural numbers using recursion

# Recursive function to find the sum of first n natural numbers

def findSum(n):

if n<=1:

return n

else:

return n + findSum(n-1)

# Driver Code

n1 = 5

n2 = 7

n3 = 6

print("n1: ", n1)

print("n2: ", n2)

print("n3: ", n3)

print("Sum of first ", n1, " natural numbers: ", findSum(n1))

print("Sum of first ", n2, " natural numbers: ", findSum(n2))

print("Sum of first ", n3, " natural numbers: ", findSum(n3))

Output:

`n1: 5 `

n2: 7

n3: 6

Sum of first 5 natural numbers: 15

Sum of first 7 natural numbers: 28

Sum of first 6 natural numbers: 21

## C Implementation to Find the Sum of First N Natural Numbers Using Recursion

Below is the C implementation to find the sum of the first n natural numbers using recursion:

`// C implementation to find the sum of`

// first n natural numbers using recursion

#include <stdio.h>

// Recursive function to find the sum of first n natural numbers

int findSum(int n)

{

if (n<=1)

{

return n;

}

else

{

return n + findSum(n-1);

}

}

// Driver code

int main()

{

int n1 = 5, n2 = 7, n3 = 6;

printf("n1: %d n", n1);

printf("n2: %d n", n2);

printf("n3: %d n", n3);

printf("Sum of first %d natural numbers: %d n", n1, findSum(n1));

printf("Sum of first %d natural numbers: %d n", n2, findSum(n2));

printf("Sum of first %d natural numbers: %d n", n3, findSum(n3));

return 0;

}

Output:

`n1: 5 `

n2: 7

n3: 6

Sum of first 5 natural numbers: 15

Sum of first 7 natural numbers: 28

Sum of first 6 natural numbers: 21

## JavaScript Implementation to Find the Sum of First N Natural Numbers Using Recursion

Below is the JavaScript implementation to find the sum of the first n natural numbers using recursion:

`// JavaScript implementation to find the sum of`

// first n natural numbers using recursion

// Recursive function to find the sum of first n natural numbers

function findSum(n) {

if (n<=1) {

return n;

} else {

return n + findSum(n-1);

}

}// Driver Code

var n1 = 5, n2 = 7, n3 = 6;

document.write("n1: " + n1 + "<br>");

document.write("n2: " + n2 + "<br>");

document.write("n3: " + n3 + "<br>");

document.write("Sum of first " + n1 + " natural numbers: " + findSum(n1) + "<br>");

document.write("Sum of first " + n2 + " natural numbers: " + findSum(n2) + "<br>");

document.write("Sum of first " + n3 + " natural numbers: " + findSum(n3) + "<br>");

Output:

`n1: 5 `

n2: 7

n3: 6

Sum of first 5 natural numbers: 15

Sum of first 7 natural numbers: 28

Sum of first 6 natural numbers: 21

## Java Implementation to Find the Sum of First N Natural Numbers Using Recursion

Below is the Java implementation to find the sum of the first n natural numbers using recursion:

`// Java implementation to find the sum of`

// first n natural numbers using recursion

public class Main

{

// Recursive function to find the sum of first n natural numbers

public static int findSum(int n)

{

if (n <= 1)

{

return n;

}

else

{

return n + findSum(n - 1);

}

}

// Driver code

public static void main(String[] args)

{

int n1 = 5, n2 = 7, n3 = 6;

System.out.println("n1: " + n1);

System.out.println("n2: " + n2);

System.out.println("n3: " + n3);

System.out.println("Sum of first " + n1 + " natural numbers: " + findSum(n1));

System.out.println("Sum of first " + n2 + " natural numbers: " + findSum(n2));

System.out.println("Sum of first " + n3 + " natural numbers: " + findSum(n3));

}

}

Output:

`n1: 5 `

n2: 7

n3: 6

Sum of first 5 natural numbers: 15

Sum of first 7 natural numbers: 28

Sum of first 6 natural numbers: 21

## Know More About Recursion

Recursive thinking is very important in programming. Sometimes the recursive solution can be simpler to read than the iterative one. You can solve many problems like the Tower of Hanoi Problem, DFS of Graph, Inorder/Preorder/Postorder Tree Traversals, etc., using recursion.

Recursion is a very powerful problem-solving strategy. Nowadays it’s also extensively used in functional programming. You must know about the basics of recursion and how you can apply it in your programming endeavors.

Read Next

**About The Author**