Given a number n, find sum of first n natural numbers. To calculate the sum, we will use a recursive function recur_sum().
Examples :
Input : 3 Output : 6 Explanation : 1 + 2 + 3 = 6 Input : 5 Output : 15 Explanation : 1 + 2 + 3 + 4 + 5 = 15
Below is code to find the sum of natural numbers up to n using recursion :
C++
// C++ program to find the // sum of natural numbers up // to n using recursion #include <iostream> using namespace std; // Returns sum of first // n natural numbers int recurSum(int n) { if (n <= 1) return n; return n + recurSum(n - 1); } // Driver code int main() { int n = 5; cout << recurSum(n); return 0; } |
Java
// Java program to find the // sum of natural numbers up // to n using recursion import java.util.*; import java.lang.*; class GFG { // Returns sum of first // n natural numbers public static int recurSum(int n) { if (n <= 1) return n; return n + recurSum(n - 1); } // Driver code public static void main(String args[]) { int n = 5; System.out.println(recurSum(n)); } } // This code is contributed by Sachin Bisht |
Python
# Python code to find sum # of natural numbers upto # n using recursion # Returns sum of first # n natural numbers def recurSum(n): if n <= 1: return n return n + recurSum(n - 1) # Driver code n = 5print(recurSum(n)) |
C#
// C# program to find the // sum of natural numbers // up to n using recursion using System; class GFG { // Returns sum of first // n natural numbers public static int recurSum(int n) { if (n <= 1) return n; return n + recurSum(n - 1); } // Driver code public static void Main() { int n = 5; Console.WriteLine(recurSum(n)); } } // This code is contributed by vt_m |
PHP
<?php // PHP program to find the // sum of natural numbers // up to n using recursion // Returns sum of first // n natural numbers function recurSum($n) { if ($n <= 1) return $n; return $n + recurSum($n - 1); } // Driver code $n = 5; echo(recurSum($n)); // This code is contributed by Ajit. ?> |
Javascript
<script> // JavaScript program to find the // sum of natural numbers // up to n using recursion // Returns sum of first // n natural numbers function recurSum(n) { if (n <= 1) return n; return n + recurSum(n - 1); } // Driver code let n = 5; document.write(recurSum(n)); // This code is contributed by mohan </script> |
Output :
15
Time complexity : O(n)
Auxiliary space : O(n)
To solve this question , iterative approach is the best approach because it takes constant or O(1) auxiliary space and the time complexity will be same O(n).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
