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 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
using namespace std;
// Recursive function to find the sum of first n natural numbers
int findSum(int n)
{
if (n {
return n;
}
else
{
return n + findSum(n-1);
}
}
// Driver code
int main()
{
int n1 = 5, n2 = 7, n3 = 6;
cout cout cout cout cout cout 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 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
// Recursive function to find the sum of first n natural numbers
int findSum(int n)
{
if (n {
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 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:
// 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 {
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.