🔄 Recursion in Data Structures & Algorithms

**Recursion** is a technique where a **function calls itself** to solve a problem by breaking it down into **smaller subproblems**.

⚡ Why Use Recursion?

  • 📌 **Simplifies Complex Problems** - Reduces code complexity.
  • ⚡ **Backtracking Algorithms** - Used in **DFS, Maze Solving, Sudoku, N-Queens.**
  • 📚 **Tree & Graph Traversals** - Used in **Preorder, Inorder, Postorder.**
  • 🔄 **Converts Loops into Elegant Code** - Helpful in **sorting algorithms.**

🔁 How Recursion Works?

Recursion follows the **Divide & Conquer approach**, solving problems in **two steps:**

  • ✅ **Base Case** - The condition where recursion stops.
  • ♻️ **Recursive Case** - The function calls itself with a smaller problem.

🛠️ Example: Factorial of a Number


                int factorial(int n) {
                    if (n == 0) return 1; // Base Case
                    return n * factorial(n - 1); // Recursive Case
                }

🔄 Types of Recursion

🔹 1. Direct Recursion

A function calls itself directly.


                void func() {
                    func();  // Direct self-call
                }

🔸 2. Indirect Recursion

Two or more functions call each other.


                void A() { B(); }
                void B() { A(); }

🔄 3. Tail Recursion

Recursive call is the **last statement** in the function.


                void tailRecursion(int n) {
                    if (n == 0) return;
                    tailRecursion(n - 1);
                }

🔃 4. Non-Tail Recursion

Recursive call is **not the last statement**.


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

⚙️ Recursive vs Iterative Approaches

Some problems can be solved using both **recursion and iteration**.

Aspect Recursion Iteration
Code Simplicity ✅ Simple & clean ❌ May require more lines
Time Complexity ⚠️ May be **O(2ⁿ)** (Exponential) ⚡ Usually **O(n)** (Linear)
Memory Usage ⚠️ Uses **stack memory (O(n))** ✅ Uses **constant memory (O(1))**
Performance ❌ May cause **Stack Overflow** ✅ More efficient for large inputs

📊 Applications of Recursion

  • 🌲 **Tree Traversals** - Used in **Binary Trees & Graphs.**
  • 🎭 **Backtracking Problems** - Used in **N-Queens, Maze Solving.**
  • 🔍 **Divide & Conquer Algorithms** - Used in **Merge Sort, Quick Sort.**
  • 🔄 **Dynamic Programming** - Used in **Fibonacci, Knapsack Problem.**

✅ Advantages & ❌ Disadvantages

  • ✅ **Reduces Code Complexity** - Easier to understand.
  • ✅ **Great for Tree & Graph Problems** - Simplifies traversal.
  • ❌ **Higher Memory Usage** - Uses function call stack.
  • ❌ **May Cause Stack Overflow** - If base case is missing.

🔗 Next Topics