Table of Contents

ToggleIn 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**:

**Function Definition:**- Define a function
`sumOfNaturalNumbers`

that takes an integer`n`

as its parameter.

- Define a function
**Base Case Check:**- Check if
`n`

is 0.- If true, return 0 (the sum of no numbers is 0).

- Check if
**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`

.

- The result of the recursive call represents the sum of the natural numbers from 1 to

- If
**Add and Return:**- Add the current
`n`

to the result of the recursive call. - Return the sum as the final result.

- Add the current

## 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

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 **sumOfNaturalNumbers**`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.