Sum of Natural Numbers using Recursion in C

In this blog post, we will see how to write Sum of Natural Numbers using Recursion in C with detailed explanation.

Before we start let’s understand few basic.

What is Formula for Sum of Natural Numbers ?

The formula for the sum of the first n natural numbers is given by:

This formula is also known as the arithmetic series formula.

To write a Sum of Natural Numbers using Recursion in C Using Recursion you can follow this algorithm and corresponding pseudo code.

Algorithm:

1. Function Definition:
   • Define a function sumOfNaturalNumbers that takes an integer n as its parameter.
2. Base Case Check:
   • Check if n is 0.
     • If true, return 0 (the sum of no numbers is 0).
3. Recursive Case:
   • If n is greater than 0, recursively call sumOfNaturalNumbers with the argument n - 1.
     • The result of the recursive call represents the sum of the natural numbers from 1 to n - 1.
4. Add and Return:
   • Add the current n to the result of the recursive call.
   • Return the sum as the final result.

Recursive Relation

f(n) = n + f(n-1)

Sum of Natural Numbers using Recursion in C

#include <stdio.h>

// Function to calculate sum of natural numbers using recursion
int sumOfNaturalNumbers(int n) {
    // Base case: sum of 0 natural numbers is 0
    if (n == 0) {
        return 0;
    } else {
        // Recursive case: sum(n) = n + sum(n-1)
        return n + sumOfNaturalNumbers(n - 1);
    }
}

int main() {
    // Example: Calculate sum of first 5 natural numbers
    int number = 5;
    int result = sumOfNaturalNumbers(number);

    printf("Sum of first %d natural numbers is: %d\n", number, result);

    return 0;
}

Output

Code Explanation

In this example, the sumOfNaturalNumbers function is defined to calculate the sum of natural numbers using recursion. The base case checks if the input is 0, and if so, returns 0. Otherwise, it recursively calls itself with the argument n - 1 until reaching the base case.

The final result is the sum of the natural numbers from 1 to the input value. The program then calculates and prints the sum of the first 5 natural numbers as an example.

Dry Run

The execution flow for the input value as 5 would unfold as follows:

To understand it better let’s dry run the provided C program for calculating the sum of natural numbers using recursion with the input value of 5:

Main Function:

• Call the sumOfNaturalNumbers function with 5 as an argument.

sumOfNaturalNumbers Function (n = 5):

• Check if n is 0 (Base case not met, as n = 5).
• Recursively call sumOfNaturalNumbers with n - 1 (4).

sumOfNaturalNumbers Function (n = 4):

• Check if n is 0 (Base case not met, as n = 4).
• Recursively call sumOfNaturalNumbers with n - 1 (3).

sumOfNaturalNumbers Function (n = 3):

• Check if n is 0 (Base case not met, as n = 3).
• Recursively call sumOfNaturalNumbers with n - 1 (2).

sumOfNaturalNumbers Function (n = 2):

• Check if n is 0 (Base case not met, as n = 2).
• Recursively call sumOfNaturalNumbers with n - 1 (1).

sumOfNaturalNumbers Function (n = 1):

• Check if n is 0 (Base case not met, as n = 1).
• Recursively call sumOfNaturalNumbers with n - 1 (0).

sumOfNaturalNumbers Function (n = 0):

• Base case met (n = 0), return 0.

Backtracking:

• The recursive call for n = 0 returns 0.
• Add the current n (1) to the result of the recursive call (0) in the n = 1 frame, returning 1.
• Add the current n (2) to the result of the recursive call (1) in the n = 2 frame, returning 3.
• Add the current n (3) to the result of the recursive call (3) in the n = 3 frame, returning 6.
• Add the current n (4) to the result of the recursive call (6) in the n = 4 frame, returning 10.
• Add the current n (5) to the result of the recursive call (10) in the n = 5 frame, returning 15.

So, the sum of the first 5 natural numbers ((1 + 2 + 3 + 4 + 5)) is calculated as 15 using recursion in the provided C program.

If you liked this post you can checkout other C Programs.

FAQ

Why is the base case necessary in the recursive function for summing natural numbers?

The base case is crucial to prevent infinite recursion. Without it, the function would keep calling itself indefinitely, leading to a stack overflow. The base case ensures the recursion stops and provides a final result.

Can this recursive approach be used for large values of ‘n’?

While recursion is an elegant way to express the sum of natural numbers, it may lead to a stack overflow for extremely large values of ‘n’ due to the depth of recursive calls. In such cases, an iterative approach or other mathematical formulas might be more suitable.