C++ Program to Find the Sum of Natural Numbers Using Recursion

by

Calculating the sum of natural numbers is a common problem in mathematics and computer science. The sum of the first n natural numbers is given by the formula 

S = \frac{n(n + 1)}{2}

In this article, we will explore the concept of recursion and demonstrate how to use it to find the sum of natural numbers in C++.

Prerequisites

Before diving into the example, it’s essential to have a basic understanding of:

  • Functions and their syntax in C++
  • The concept of recursion
  • Basic input and output operations in C++
  • Compiling and running a C++ program

Understanding Recursion

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. A recursive function has two main components:

  1. Base Case: The condition under which the recursion ends.
  2. Recursive Case: The part of the function where it calls itself with a smaller or simpler subproblem.

In the case of finding the sum of natural numbers, the base case is when nnn is 0, as the sum of the first 0 natural numbers is 0. The recursive case involves adding nnn to the sum of the first n−1n-1n−1 natural numbers.

C++ Program to Find the Sum of Natural Numbers Using Recursion

C++
#include <iostream>
using namespace std;

// Recursive function to find the sum of natural numbers
int sumOfNaturalNumbers(int n) {
    if (n <= 0) { // Base case
        return 0;
    } else {
        return n + sumOfNaturalNumbers(n - 1); // Recursive case
    }
}

int main() {
    int num;
    cout << "Enter a positive integer: ";
    cin >> num;
    
    if (num < 0) {
        cout << "Please enter a positive integer." << endl;
    } else {
        cout << "Sum of the first " << num << " natural numbers is: " << sumOfNaturalNumbers(num) << endl;
    }
    
    return 0;
}

Output

C++
Enter a positive integer: 5
Sum of the first 5 natural numbers is: 15

Explanation:

  1. Function Definition:
    • The sumOfNaturalNumbers function takes an integer n as its parameter.
    • The base case checks if n is less than or equal to 0. If true, it returns 0.
    • The recursive case returns n plus the result of sumOfNaturalNumbers(n - 1).
  2. Main Function:
    • The program prompts the user to enter a positive integer.
    • It reads the input number.
    • It checks if the number is negative and prompts the user to enter a positive integer if it is.
    • If the number is non-negative, it calls the sumOfNaturalNumbers function and prints the result.

Example Runs

Example 1: Finding Sum of First 4 Natural Numbers

C++
Enter a positive integer: 4
Sum of the first 4 natural numbers is: 10

Explanation:

  • The function calls proceed as follows: sumOfNaturalNumbers(4), sumOfNaturalNumbers(3), sumOfNaturalNumbers(2), sumOfNaturalNumbers(1), sumOfNaturalNumbers(0).
  • The results are: sumOfNaturalNumbers(0) = 0, sumOfNaturalNumbers(1) = 1 + 0 = 1, sumOfNaturalNumbers(2) = 2 + 1 = 3, sumOfNaturalNumbers(3) = 3 + 3 = 6, sumOfNaturalNumbers(4) = 4 + 6 = 10.

Example 2: Finding Sum of First 0 Natural Numbers

C++
Enter a positive integer: 0
Sum of the first 0 natural numbers is: 0

Explanation:

  • The base case is met immediately, and the function returns 0.

Conclusion

Recursion provides an elegant solution for calculating the sum of natural numbers. By breaking down the problem into smaller subproblems, recursive functions can handle complex tasks with concise code. However, it’s crucial to ensure that a base case is defined to prevent infinite recursion.