Sum of First N Natural Numbers Using Recursion

Given a number n, find the sum of the first n natural numbers using recursion.
Examples:

Input: n = 3
Output: 6
Explanation: 1 + 2 + 3 = 6

Input: n = 5
Output: 15
Explanation: 1 + 2 + 3 + 4 + 5 = 15

Approach:

To find the sum of the first n natural numbers using recursion, we define a function recurSum(n-1).

At each step, the function adds the current number n to the sum of all smaller numbers by calling recurSum(n-1).
The recursion continues until the base case is reached, where n = 0, at which point the function returns 0 to stop further calls.
As the recursive calls return back, the intermediate sums are combined step by step, eventually producing the total sum of the first n natural numbers.

#include <iostream> using namespace std; int recurSum(int n){    // base case  if (n == 0)  return 0;    // recursive case  return n + recurSum(n - 1); } int main(){  int n = 3;  cout << recurSum(n);  return 0; } 

class GFG {  public static int recurSum(int n){    // base case  if (n == 0)  return 0;    // recursive case  return n + recurSum(n - 1);  }  public static void main(String args[]){  int n = 3;  System.out.println(recurSum(n));  } } 

def recurSum(n): # base case if n == 0: return 0 # recursive case return n + recurSum(n - 1) # Driver code if __name__ == "__main__": n = 3 print(recurSum(n)) 

using System; class GFG {  public static int recurSum(int n){    // base case  if (n == 0)  return 0;    // recursive case  return n + recurSum(n - 1);  }    public static void Main(){  int n = 3;  Console.WriteLine(recurSum(n));  } } 

function recurSum(n) {    // base case  if (n == 0)  return 0;    // recursive case  return n + recurSum(n - 1); } // Driver code let n = 3; console.log(recurSum(n)); 

6

Time Complexity: O(n)
Space Complexity: O(n) Recursive Space