Sum of First N Numbers

Problem Statement

Given a positive integer n, write a function to calculate the sum of the first n natural numbers using recursion.

Examples

Example 1:

Input: n = 5
Output: 15

Explanation: The sum of the first 5 natural numbers is 
1+2+3+4+5=15.

Example 2:

Input: n = 10
Output: 55

Explanation: The sum of the first 10 natural numbers is
1+2+3+...+10=55.

Different Approaches

The sum of the first n natural numbers can be mathematically represented as:

S(n) = 1+2+3+...+n = n(n+1)/2

This formula gives the sum in constant time, but the problem asks us to use recursion, which is a fundamental technique in programming. The recursive approach to the sum of first n natural numbers is based on breaking the problem into smaller sub-problems.

Recursive Insight:

We know that: S(n) = n + S(n−1)

This recursive equation says that the sum of the first n natural numbers is n added to the sum of the first n-1 numbers.

Base Case:

The recursion must terminate at some point, and the natural base case is when n = 0, for which the sum is simply 0:

S(0) = 0

1️⃣ Recursive Approach

#include<iostream>
using namespace std;

// Function to calculate the sum of first n natural numbers using recursion
int sumOfFirstN(int n) {
    // Base case
    if (n == 0) {
        return 0;
    }
    // Recursive case
    return n + sumOfFirstN(n - 1);
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    
    int result = sumOfFirstN(n);
    cout << "Sum of first " << n << " natural numbers is: " << result << endl;
    
    return 0;
}

Recursive Tree:

sumOfFirstN(5) = 5 + sumOfFirstN(4)
               = 5 + (4 + sumOfFirstN(3))
               = 5 + (4 + (3 + sumOfFirstN(2)))
               = 5 + (4 + (3 + (2 + sumOfFirstN(1))))
               = 5 + (4 + (3 + (2 + (1 + sumOfFirstN(0)))))
               = 5 + (4 + (3 + (2 + (1 + 0))))
               = 15

Complexity Analysis:

• Time Complexity: O(n)
  • In the recursive approach, the function calls itself n times, reducing the size of the problem by 1 at each step. Hence, the time complexity is: O(n)
• Space Complexity: O(n)
  • Each recursive call uses additional stack space to store the function call. Since there are n function calls, the space complexity is: O(n).