LeetCode Solutions← Back to Patterns
Recursion & BacktrackingMedium
Recursion
Break a problem into identical smaller subproblems and combine results.
How it works
Recursion solves a problem by expressing it in terms of a smaller version of itself. Every recursive solution has two parts: (1) Base case — the simplest input that can be answered directly without recursion. (2) Recursive case — reduce the problem to one or more smaller subproblems, recurse, and combine results. Recursion is the natural language for tree and graph problems because a tree is itself defined recursively (a node with subtrees). The call stack implicitly maintains state, so you don't need explicit data structures. When subproblems overlap, add memoization to cache results and avoid redundant computation — this turns exponential recursion into polynomial DP.
Interactive Playground
f(4) calls f(3). Push frame onto call stack.
Speed
When to use
- Tree or graph traversal
- Divide and conquer algorithms
- Problems with overlapping substructure (memoization)
✅Tips
1Always identify the base case first — it prevents infinite recursion and defines the simplest answer.
2Think about what the function returns and trust that it works for smaller inputs before writing the recursive case.
3Add memoization (HashMap of input → result) if you notice the same subproblem being solved multiple times.
4Draw the recursion tree for small inputs to understand the branching factor and depth.
❌Common Mistakes
!Missing or incorrect base case — causes infinite recursion and stack overflow.
!Returning the wrong value from the recursive case — each call must return a meaningful result.
!Not memoizing overlapping subproblems — leads to exponential time complexity (e.g., naive Fibonacci).
!Mutating shared state inside recursion without restoring it — causes incorrect results in backtracking variants.
💡 Key Insight:Trust that the recursive call solves the subproblem — define the base case clearly.