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.

Related: What Is a Function in Programming?

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:

Related: Dynamic Programming: Examples, Common Problems, and Solutions

        # 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 + "
");
document.write("n2: " + n2 + "
");
document.write("n3: " + n3 + "
");

document.write("Sum of first " + n1 + " natural numbers: " + findSum(n1) + "
");
document.write("Sum of first " + n2 + " natural numbers: " + findSum(n2) + "
");
document.write("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
    

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:

Related: What Is a Recursive Function, and How Do You Create One in Java?

        // 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.