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:
To find the sum of the first n natural numbers, observe and apply the following pseudocode:
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:
Output:
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:
Output:
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:
Output:
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:
Output:
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:
Output:
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.
