Recursion

Recursion is a technique where a function calls itself to solve smaller instances of a problem. A base condition is necessary to stop the recursion; otherwise, it will continue infinitely.

Recursion is a concept where a function solves a problem by calling itself with a smaller version of the same problem. A stopping condition (base case) is necessary to prevent infinite recursion.

Factorial Calculation

5! = 5 × 4 × 3 × 2 × 1 = 120

Example:

#include <stdio.h>

// Function to calculate factorial using recursion
int factorial(int n) {
    if (n == 0) // Base condition
        return 1;
    return n * factorial(n - 1); // Recursive call
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d", num, factorial(num));
    return 0;
}

Output:

Factorial of 5 is 120

Explanation:

If n is 0, return 1 (base condition).
Otherwise, multiply n by the factorial of n-1.
The function keeps calling itself until n becomes 0, at which point the recursion stops and results are returned step by step

Real-Life Example: Russian Dolls (Matryoshka Dolls)

Imagine you have a set of Russian dolls, where each doll contains a smaller doll inside it. To reach the smallest doll:
1. You open the largest doll.
2. Take out the smaller doll inside.
3. Repeat the process until you reach the smallest doll, which cannot be opened (base case).

This is just like recursion:

The action of opening a doll and repeating it for the next smaller doll represents the function calling itself. The smallest doll, which cannot be opened, represents the base case where recursion stops.

Real-Life Example in Computing: File System Navigation

When you open a folder on a computer, it may contain:
1. Files
2. More folders (which can contain more files or folders)

A program that lists all files in a folder recursively works like this:
1. Open the folder.
2. List all files.
3. If a subfolder is found, open that and repeat the process.
4. Stop when there are no more folders to open (base case).

Sum of first 5 natural numbers

5 + 4 + 3 + 2 + 1 + 0 = 15

#include <stdio.h>

// Recursive function to find sum of first n natural numbers
int sumNatural(int n) {
    if (n == 0) 
        return 0;  // Base case
    return n + sumNatural(n - 1);  // Recursive call
}

int main() {
    int num = 5;
    printf("Sum of first %d natural numbers is: %d", num, sumNatural(num));
    return 0;
}

Output:

Sum of first 5 natural numbers is: 15