Introduction to Recursion

In computer programming, sometimes a function needs to call itself to solve a problem — this is called Recursion.

What is Recursion?

Recursion is the process where a function calls itself to solve a smaller version of the original problem.

This type of function is known as a recursive function.

Real Example in C: Sum of First N Natural Numbers

Let’s write a program in C language to find the sum of first n natural numbers using recursion.

C Code:

#include <stdio.h>

int sum(int n) {

    if (n == 1)  // Base case

        return 1;

    else

        return n + sum(n - 1);  // Recursive case

}

int main() {

    int number;

    printf("Enter a positive number: ");

    scanf("%d", &number);

    int result = sum(number);

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

    return 0;

}

How Does This Work?

• If you enter 4, the calls will be:
  sum(4) → 4 + sum(3)
  sum(3) → 3 + sum(2)
  sum(2) → 2 + sum(1)
  sum(1) → returns 1 (base case)
  
  

Then it adds up: 4 + 3 + 2 + 1 = 10

Steps to Implement Recursion

Step 1: Define a Base Case

This is the simplest condition where recursion stops.
In the code: if (n == 1) return 1;

Step 2: Write a Recursive Case

This is where the function calls itself for a smaller input.
 In the code: return n + sum(n - 1);

Step 3: Make Sure It Ends

Every recursive function must reach the base case to stop.
This avoids infinite recursion (a crash!).

Step 4: Combine the Results

Each call returns a number, and they all add up to give the final answer.

Why is Recursion Useful?

• Solves complex problems by breaking them into smaller ones

• Makes some problems (like trees, graphs, and puzzles) much easier

• Recursion is used in Divide and Conquer algorithms like Merge Sort

• Foundation for Dynamic Programming

What is a Base Condition?

A base condition is the stopping rule of a recursive function.
Without it, the function would keep calling itself forever.

In our code:
if (n == 1) is the base condition.

How Recursion Solves Problems?

• Break the big problem into smaller parts

• Call the same function again with a smaller input

• Stop when reaching the base case

• Combine all returned values to get the final result

Final Summary:

Final Thought:

In C programming, recursion helps you solve big problems by dividing them into smaller versions of the same problem. Just remember to set a base case to stop it.