C Program to Find the Sum of Natural Numbers Using Recursion

Calculating the sum of natural numbers using recursion is a fundamental programming exercise that helps in understanding the concept of recursion and function calls. This article will cover various C Program to Find the Sum of Natural Numbers Using Recursion complete with examples, explanations, and outputs.

Prerequisites

Before diving into the examples, you should be familiar with:

• Basic C syntax and structure.
• Functions and recursion in C.
• Basic understanding of natural numbers.

Understanding the Problem

The task is to calculate the sum of the first n natural numbers using a recursive function. Natural numbers are positive integers starting from 1.

For example, the sum of the first 5 natural numbers is:

1+2+3+4+5=15

Example 1: Basic Recursion

1.1 Explanation

In this example, we will create a simple recursive function to calculate the sum of the first n natural numbers. The base case is when n is 1. For any other value of n, the function calls itself with the value n-1.

1.2 Program: Basic Recursion

#include <stdio.h>

int sumOfNaturalNumbers(int n);

int main() {
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    printf("Sum of the first %d natural numbers is: %d\n", num, sumOfNaturalNumbers(num));
    return 0;
}

int sumOfNaturalNumbers(int n) {
    if (n == 1)
        return 1;
    else
        return n + sumOfNaturalNumbers(n - 1);
}

1.3 Output

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

Example 2: Tail Recursion

2.1 Explanation

Tail recursion is an optimized form of recursion where the recursive call is the last operation in the function. This can help in reducing the stack space used by the program.

2.2 Program: Tail Recursion

#include <stdio.h>

int sumOfNaturalNumbers(int n, int accumulator);

int main() {
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    printf("Sum of the first %d natural numbers is: %d\n", num, sumOfNaturalNumbers(num, 0));
    return 0;
}

int sumOfNaturalNumbers(int n, int accumulator) {
    if (n == 0)
        return accumulator;
    else
        return sumOfNaturalNumbers(n - 1, accumulator + n);
}

2.3 Output

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

Example 3: Using Static Variable

3.1 Explanation

In this example, we will use a static variable to keep track of the sum. Static variables retain their value between function calls, making it easier to accumulate the sum without passing it as an argument.

3.2 Program: Using Static Variable

#include <stdio.h>

int sumOfNaturalNumbers(int n);

int main() {
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    printf("Sum of the first %d natural numbers is: %d\n", num, sumOfNaturalNumbers(num));
    return 0;
}

int sumOfNaturalNumbers(int n) {
    static int sum = 0;
    if (n == 0)
        return sum;
    sum += n;
    return sumOfNaturalNumbers(n - 1);
}

3.3 Output

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

Conclusion

In this article, we explored various ways to calculate the sum of natural numbers using recursion in C. The examples covered different techniques:

1. Basic Recursion: Simple recursive approach.
2. Tail Recursion: Optimized recursion for better stack management.
3. Using Static Variable: Accumulating sum using a static variable.

Each example provided a different perspective on solving the problem, demonstrating the flexibility and power of recursion. By understanding these examples, you can tackle similar problems and optimize your solutions for better performance.