🔁 Recursion in C - Complete Guide

What is Recursion?

Recursion is a technique where a function calls itself to solve a problem in smaller sub-parts.

void function() {
    // logic
    function();  // recursive call
}

Every recursive function must have a base case to stop further recursive calls.

Why Use Recursion?

When the problem can be divided into smaller sub-problems.
To write cleaner and more readable code for nested/recursive structures.
Some problems are naturally recursive (e.g. tree traversal).

Types of Recursion

Direct Recursion: Function calls itself directly.
Indirect Recursion: Function A calls B, which calls A again.
Tail Recursion: Recursive call is the last thing done.
Head Recursion: Recursive call happens first.
Tree Recursion: Function calls itself multiple times.

How Recursion Works

Every recursive call adds a new frame to the call stack. Once the base case is reached, the stack unwinds returning values.

Example: Factorial

#include <stdio.h>

int factorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

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

Breakdown:

factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
...
factorial(0) → 1 (base case)

Real Life Analogies

📦 Russian Dolls (one inside another)
🪞 Mirrors facing each other
🧗 Climbing stairs recursively
🗼 Tower of Hanoi

Practical Use Cases

File system traversal
Solving puzzles like Sudoku, N-Queens
Tree and Graph traversal
Backtracking problems
Sorting: Merge Sort, Quick Sort

Recursion in DSA

Trees: Inorder, Preorder, Postorder
Graphs: DFS
Divide & Conquer: Merge Sort, Quick Sort
Backtracking: N-Queens, Maze Solver
Dynamic Programming: Memoization

When Not to Use Recursion

Very deep recursion can cause stack overflow
Iteration may be more efficient in some cases
Resource-constrained environments

Summary

🔁 Recursion: Function calling itself
🧠 Base Case: Must exist to prevent infinite calls
📦 Applications: DSA, file systems, games, puzzles
⚠️ Be cautious: Stack depth and memory usage