Sum of First 5 Natural Numbers in C: Understanding Recursion Step by Step

🔢 Problem Statement

Write a C program to find the sum of the first 5 natural numbers.

The problem will be solved in two different ways:

• Part 1: Using a loop (without recursion)
• Part 2: Using a recursive function (with recursion)

💡 Goal: First understand the ordinary solution, then see how the same problem can be solved using recursion.

🔄 What is Recursion?

Recursion is a technique in which a function calls itself to solve a problem. The function keeps calling itself with a smaller or simpler part of the problem until it reaches a stopping condition. That stopping condition is called the base condition.

🌳 Real-life example: Imagine looking at two mirrors facing each other. You see your reflection, then another reflection inside it, and so on. Another simple example is opening a folder that contains another folder, which contains another folder. You keep opening the next folder until there are no more folders. In programming, recursion works in a similar way—the function repeats the same task until a condition tells it to stop.

🌍 Real-Life Applications of Recursion

Recursion is not just a programming concept. Many real-world problems have a repeating structure, where the same type of task is performed again and again on a smaller part of the problem.

• 📁 Folders and subfolders: A folder can contain other folders, and those folders can contain more folders. A program can recursively explore all the files and folders.
• 🌳 Family trees: To find information about a person’s parents, grandparents, great-grandparents, and so on, the same operation can be repeated for each generation.
• 🗂️ Searching files: When a computer searches through a folder and all its subfolders, it can use recursion to visit each folder one by one.
• 🧩 Solving puzzles and mazes: A computer can try one possible path, continue step by step, and go back when a path does not work. This idea is used in solving mazes, puzzles, and similar problems.
• 🌐 Web pages and links: A website can contain sections, which contain more sections or linked information. Programs can recursively process such hierarchical structures.
• 🔍 Searching in a tree: Computer programs use recursion to search structures such as folders, organization charts, and decision trees.

🟢 Part 1: Find the Sum Without Function & No Recursion

In this approach, we use a for loop to calculate the sum of the first 5 natural numbers.

#include <stdio.h>

int main()
{
    int i, sum = 0;

    for(i = 1; i <= 5; i++)
    {
        sum = sum + i;
    }

    printf("Sum = %d", sum);

    return 0;
}

🟢 Part 2: Find the Sum Without Recursion, but uses Function

First, let us solve the problem using a normal C function. The function uses a for loop to calculate the sum of the first 5 natural numbers.

#include <stdio.h>

int sum(int n)
{
    int i, total = 0;

    for(i = 1; i <= n; i++)
    {
        total = total + i;
    }

    return total;
}

int main()
{
    int result;

    result = sum(5);

    printf("Sum = %d", result);

    return 0;
}

⚙️ How It Works

The statement:

result = sum(5);

This statement calls the function sum() and passes 5 as the argument.

Inside the function:

for(i = 1; i <= n; i++)
{
    total = total + i;
}

The for loop adds the values one by one.

Finally:

return total;

The function returns 15 to main().

So:

🔄 Part 3: Find the Sum Using Recursion

Now, let us solve the same problem using a recursive function. The function sum() calls itself with a smaller value until it reaches the base condition.

#include <stdio.h>

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

int main()
{
    int result;

    result = sum(5);

    printf("Sum = %d", result);

    return 0;
}

🔄 How Recursion Works

When we call:

result = sum(5);

the function sum() calls itself with a smaller value:

sum(5)
= 5 + sum(4)
= 5 + 4 + sum(3)
= 5 + 4 + 3 + sum(2)
= 5 + 4 + 3 + 2 + sum(1)
= 5 + 4 + 3 + 2 + 1 + sum(0)

When n becomes 0, the base condition executes:

if(n == 0)
    return 0;

Now the function calls return in reverse order:

Therefore:

🔴 Every recursive solution must have a
BASE CONDITION
to stop the recursion.

int sum(int n)
{
    if(n == 0)
        return 0;

    return n + sum(n - 1);
}

Here, if(n == 0) is the base condition. When n becomes 0, the function stops calling itself and returns 0.

📚 Understanding Recursion Using a Stack

When a function is called, the computer creates a small memory area called a stack frame to keep information about that function call. In recursion, every time the function calls itself, a new stack frame is created.

Recursion works in a similar way. Consider our function:

return n + sum(n - 1);

When we call sum(5), the function does not immediately finish. It needs the answer from sum(4), so it calls sum(4). Then sum(4) needs sum(3), and so on.

🔄 Returning Back: Unwinding the Recursive Calls

When the recursive function reaches its base condition, it stops going deeper. Now the function calls begin to return one by one. This process is called unwinding the recursion.

The recursion stops when:

At this point, sum(0) returns 0. Then the previous function call, sum(1), can continue its calculation.