Recursion Problems (50)
Problems tagged with Recursion
About Recursion
Recursion is a fundamental technique in data structures and algorithms where a function solves a problem by calling itself on smaller subproblems. Instead of writing complex loops, recursion breaks a task into simpler pieces until it reaches a base case—a condition where the function stops calling itself. This divide-into-smaller-parts approach makes recursion especially powerful for problems involving hierarchical structures, repeated patterns, and exhaustive exploration.
Recursion is heavily tested in technical interviews because it reveals how well a candidate understands problem decomposition and algorithmic thinking. Many classic interview problems—from generating permutations to traversing trees—are easiest to express recursively. Mastering recursion also prepares you for advanced topics such as Divide and Conquer and Dynamic Programming, both of which build on recursive problem structures.
Common recursion patterns appear across many algorithm categories. For example:
- Tree traversal problems rely on recursion to explore nodes naturally, which connects closely with Binary Tree and Depth-First Search techniques.
- Backtracking uses recursion to explore all possible choices while undoing decisions, a key idea in problems like permutations, combinations, and N-Queens. Learn more in Backtracking.
- Optimization with caching transforms recursive solutions into efficient algorithms using Memoization.
You should use recursion when a problem can be expressed as repeated smaller instances of itself—such as traversing trees, computing combinations, exploring search spaces, or implementing divide-and-conquer algorithms like merge sort. However, recursion must always include a clear base case and careful control of the call stack to avoid infinite recursion or stack overflow.
On FleetCode, you can practice 46 carefully selected Recursion problems that build your intuition step by step—from simple factorial-style recursion to complex interview questions combining recursion with backtracking, trees, and dynamic programming.
Prerequisites
Recursive traversal is the natural way to process tree structures. Concepts like preorder, inorder, and postorder traversal rely heavily on recursion.
Recursion relies on the call stack to store function states. Understanding stack operations helps you visualize recursive calls and convert recursive solutions into iterative ones.
Backtracking extends recursion to explore all possible choices in a search space. Learning it helps with permutations, combinations, and constraint-based problems.
Many recursive algorithms follow divide-and-conquer patterns where a problem is split into smaller independent subproblems and their results are combined.
Many dynamic programming solutions start as recursive definitions and are optimized using memoization or tabulation to avoid repeated computation.
| Status | Title | Solution | Practice | Difficulty | Companies | Topics |
|---|---|---|---|---|---|---|
| 21. Merge Two Sorted Lists | Solution | Solve | Easy | Accenture+35 | ||
| 203. Remove Linked List Elements | Solution | Solve | Easy | Amazon+8 | ||
| 206. Reverse Linked List | Solution | Solve | Easy | Accenture+33 | ||
| 231. Power of Two | Solution | Solve | Easy | Amazon+10 | ||
| 234. Palindrome Linked List | Solution | Solve | Easy | Amazon+16 | ||
| 326. Power of Three | Solution | Solve | Easy | Amazon+5 | ||
| 342. Power of Four | Solution | Solve | Easy | Amazon+7 | ||
| 509. Fibonacci Number | Solution | Solve | Easy | Accenture+15 | ||
| 3304. Find the K-th Character in String Game I | Solution | Solve | Easy | Amazon+4 | ||
| 3483. Unique 3-Digit Even Numbers | Solution | Solve | Easy | Amazon+2 |
Practice by Difficulty
Start Easy, progress to Hard.
Related Topics
Frequently appear alongside Recursion.
FAQ
Common questions about Recursion.
Is Recursion important for FAANG interviews?
Yes. Recursion appears frequently in FAANG interviews, especially in tree traversal, backtracking, and divide-and-conquer problems. Many dynamic programming questions also start with a recursive formulation before optimization.
What is the best way to learn Recursion for DSA?
Start by understanding base cases and the call stack, then practice simple problems like factorial or Fibonacci. Gradually move to tree traversal, subset generation, and backtracking problems, and finally learn how recursion connects to dynamic programming.
What are the most common Recursion patterns in DSA?
Common recursion patterns include divide-and-conquer, backtracking, recursive tree traversal, recursion with memoization, and building solutions using smaller subproblems. Recognizing these patterns helps solve many interview questions quickly.
Why do recursive solutions sometimes cause stack overflow?
Stack overflow occurs when recursion depth becomes too large because each call adds a frame to the call stack. This usually happens when a base case is missing or when recursion runs on very large inputs without optimization.
What are the best Recursion problems for coding interviews?
The best recursion interview problems include factorial and Fibonacci variations, generating permutations or combinations, N-Queens, subset generation, and recursive tree traversals. Interview platforms typically include 30–50 representative recursion problems covering backtracking, divide-and-conquer, and memoized recursion.
How many Recursion problems should I solve to master the topic?
Most candidates gain strong recursion skills after solving about 30–60 well-chosen problems. Focus on patterns such as base cases, recursion trees, backtracking, and memoization rather than memorizing solutions.