Data Structures and Algorithms in C (DSA)

📘 Recursion and Stack Memory

Recursion is a powerful concept where a function calls itself to solve smaller subproblems. It’s commonly used in algorithms like factorial, Fibonacci, tree traversal, and divide-and-conquer strategies like merge sort.

🔁 What is Recursion?

Recursion is a technique where the solution to a problem depends on solutions to smaller instances of the same problem. It typically involves a base case and a recursive case.

✅ Example: Factorial of a Number

int factorial(int n) {
    if (n == 0 || n == 1) return 1;   // base case
    return n * factorial(n - 1);      // recursive call
}
  

📌 Key Components of Recursion

• Base Case: When the function stops calling itself.
• Recursive Case: The part where the function calls itself.
• Stack Frame: Each function call is stored in memory (stack).

🧠 How Stack Memory Works

In C, each function call creates a new stack frame that stores local variables and return addresses. When a function finishes, the frame is removed (popped) from the stack.

🔍 Illustration of Stack for factorial(3)

factorial(3)
 └─> factorial(2)
       └─> factorial(1)
             └─> return 1
       └─> return 2 * 1 = 2
 └─> return 3 * 2 = 6
  

🚫 Common Mistakes in Recursion

• Missing or incorrect base case → leads to infinite recursion
• Modifying global variables inside recursive calls
• Not optimizing tail calls → causes stack overflow for large inputs

🧪 Real-Life Analogy

Imagine a stack of dishes: each recursive call places a new dish on top (push), and when it finishes, it removes it (pop). You must finish the top dish before touching the next one!

⚙️ Applications of Recursion

• Mathematical Problems: Factorial, Fibonacci
• Tree Traversal: Preorder, Inorder, Postorder
• Backtracking: N-Queens, Maze Solving
• Divide-and-Conquer: Merge Sort, Quick Sort

📚 UdaanPath Tip

Practice writing both recursive and iterative versions of functions. Understand the stack trace for each and use debugging tools to see how recursion unfolds.

✅ Summary

• Recursion solves problems by breaking them into smaller parts.
• Each call uses stack memory — watch out for large recursion depths!
• Base cases are critical to stop infinite recursion.

📤 Coming Next

Next, we will dive into Mathematics for DSA (GCD, LCM, Modulo Arithmetic) — the simplest and most fundamental data structure that every programmer must master.