DSA Recursion

What is Recursion?

Recursion is a technique where a function repeatedly invokes itself to handle reduced versions of the original task.. Instead of solving everything at once, it breaks the problem into smaller chunks, solving each step by repeatedly calling itself.

This process continues until a base case is reached — a condition where the function stops calling itself. Once the base case is met, the program begins to return results step by step, solving the entire problem from the smallest unit back to the original input.

How Recursion Works

Imagine you're standing on a staircase and want to count how many steps there are. Instead of counting from the top, you ask the person below you to count the rest. That person does the same with the one below them, and so on. Eventually, the person at the bottom counts 1. That count is passed back up the chain, each adding 1 — until you have the total.

This is how recursion works — solving the smallest case and building back up.

Key Parts of a Recursive Function:

• Base Case: The specific situation where the function stops making further self-calls.
• Recursive Call: The moment the function triggers itself again with a smaller piece of the original input.
• Progression: The input must get closer to the base case with each call.

Example

#include <stdio.h>  

int factorial(int n) {     
      if (n == 0 || n == 1)  // Base case         
          return 1;     
      else         
          return n * factorial(n - 1);  // Recursive call 
}  

int main() {     
       int result = factorial(5);     
       printf("Factorial of 5 is %d\n", result);  // Output: 120     
       return 0; 
} 

Uses of Recursion

• Solving mathematical sequences like factorial, Fibonacci, or power functions.
• Tree and graph traversal in depth-first search (DFS).
• Solving puzzles like Tower of Hanoi or mazes.
• Directory/file structure navigation in operating systems.
• Parsing expressions in compilers or interpreters.

Advantages of Recursion

• Simplified logic: Functions written recursively tend to be more compact and visually easier to understand.
• Handles complex problems: Some problems are easier to express recursively (e.g., tree traversal).
• Logical structure: Mimics the natural breakdown of a problem.

Disadvantages of Recursion

• Increased memory demand: Every recursive call consumes stack space, which can add up quickly.
• Possibility of endless loops: Without a valid stopping condition, the recursion may continue forever and cause a system failure.
• Slower in some cases: Iterative solutions can be more efficient for simple problems.

Recursion vs Iteration

Conclusion

Recursion plays a key role in solving problems within data structures and algorithm design. It teaches you how to think in steps, solve problems from the bottom up, and organize logic cleanly. When used carefully, it becomes a powerful tool for breaking down even the most complex challenges.