Recursion occurs when a function calls itself, directly or indirectly. It breaks a large problem into smaller sub-problems of the same nature. Every recursive function must have a Base Case to prevent infinite recursion.

Ideal for problems with tree-like structures, sorting algorithms (Merge Sort, Quick Sort), and backtracking (N-Queens, Sudoku).

• Depends on the recurrence relation.
• Simple factorial: $O(N)$
• Fibonacci (unoptimized): $O(2^N)$

cpp Standard
// Factorial using recursion
int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Recursive step
}

• Stack Overflow: Too many recursive calls without hitting a base case.
• Forgetting the base case entirely.
• Redundant calculations: Solving the same sub-problem multiple times (unoptimized).