This content originally appeared on DEV Community and was authored by Dev Cookies
Recursion is one of the most fundamental problem-solving techniques in programming. However, not every problem is a recursion problem. In interviews, many candidates struggle to decide whether recursion is the right tool. This blog will help you build intuition for when and why to use recursion.
Step 1: What is Recursion?
Recursion is when a function calls itself to solve a smaller instance of the same problem until it reaches a base case.
Example:
int factorial(int n) {
if (n == 0) return 1; // base case
return n * factorial(n - 1); // recursive step
}
Key properties of recursion:
- A base case to stop recursion.
- A recursive case that reduces the problem size.
Step 2: Checklist – Is it a Recursion Problem?
Ask yourself:
Can I break the problem into smaller versions of itself?
Example: Factorial →n! = n * (n-1)!Does the solution naturally follow a divide-and-conquer approach?
Example: Binary search, merge sort.Am I traversing hierarchical structures (trees, graphs)?
Example: Tree traversals (inorder, preorder, postorder).Am I exploring multiple choices/paths?
Example: Subsets, permutations, N-Queens → backtracking problems.
If most of these are true, recursion is likely the right choice.
Step 3: Common Patterns of Recursion Problems
1. Divide and Conquer
- Break the problem into two or more independent parts.
- Examples: Merge Sort, Quick Sort, Binary Search.
2. Tree/Graph Traversal
- Natural fit since trees/graphs are recursive data structures.
- Examples: DFS, BFS (can be recursive with DFS).
3. Backtracking
- Explore all possibilities and backtrack when a path is invalid.
- Examples: N-Queens, Sudoku solver, Subset/Permutation generation.
4. Mathematical Recurrence Relations
- Problems that directly map to recurrence.
- Examples: Factorial, Fibonacci (though inefficient without DP).
Step 4: Signs a Problem Is Not Recursion
- The problem is purely iterative (e.g., sum of numbers in an array).
- No smaller self-similar subproblem exists.
- Problem doesn’t require branching, hierarchical traversal, or divide-and-conquer.
Quick Decision Points
Problem → Can I define it in terms of smaller versions of itself?
↓ No → Not recursion
↓ Yes
Does it need hierarchical traversal OR multiple choice exploration?
↓ Yes → Use recursion
Final Words
Recursion shines in problems where self-similarity, hierarchical structures, or branching choices are present. If you can clearly define a base case and a recursive step, then recursion is often the cleanest and most elegant solution.
Start practicing by identifying whether a problem can be broken down into smaller subproblems. Once that intuition is built, spotting recursion problems in interviews becomes second nature.
This content originally appeared on DEV Community and was authored by Dev Cookies