Recursion Coding Problems: 40 Questions with Solutions
40 recursion coding problems — 9 easy · 19 medium · 12 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 40
- By difficulty: 9 easy · 19 medium · 12 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A function that calls itself on a smaller input. The problems here isolate the two things that make recursion work — a base case that stops it and a step that gets closer to it — on inputs where the recursive statement is the clearest solution, and show where an explicit stack or a loop should replace it.
New to recursion? Read the Recursion tutorial first.
How recursion works, step by step
power(2, 10)- power(2, 10) computes 2 to the 10th by halving: with h = power(x, n // 2), the answer is h * h, times one more x when n is odd. The first call cannot finish until power(2, 5) answers, so it waits on the call stack.
- power(2, 5) is pushed on top and asks for power(2, 2). Each call keeps its own n, so the call below it still remembers where it was; n halves every time, so the stack grows like log n.
- power(2, 2) is pushed on top and asks for power(2, 1). Each call keeps its own n, so the 2 calls below it still remember where they were; n halves every time, so the stack grows like log n.
- power(2, 1) is pushed on top and asks for power(2, 0). Each call keeps its own n, so the 3 calls below it still remember where they were; n halves every time, so the stack grows like log n.
- power(2, 0) hits the base case and returns 1 without calling anything: this is what stops the recursion. The stack is 5 calls deep, its deepest point.
- power(2, 0) is popped and passes 1 back up. power(2, 1) resumes with h = 1; n = 1 is odd, so it returns 1 * 1 * 2 = 2.
- power(2, 1) is popped and passes 2 back up. power(2, 2) resumes with h = 2; n = 2 is even, so it returns 2 * 2 = 4.
- power(2, 2) is popped and passes 4 back up. power(2, 5) resumes with h = 4; n = 5 is odd, so it returns 4 * 4 * 2 = 32.
- power(2, 5) is popped and passes 32 back up. power(2, 10) resumes with h = 32; n = 10 is even, so it returns 32 * 32 = 1024.
- power(2, 10) passes 1024 back to its caller and the stack empties. It took 5 calls where a loop would multiply 10 times: O(log n) calls and O(log n) stack space, because n halves on every call.
Recursion study plan
14 of the 40 Recursion problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 26 in the full list below are practice at your own pace. Then move on to Merge Sort.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
- Fibonacci Number Easy
- Power of Three Easy
- Power of Four Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Transform to Sum Tree Easy
- Decode String Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Predict the Winner Medium
- Find the Winner of the Circular Game Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Elimination Game Medium
- Count Good Numbers Medium
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Number of Digit One Hard
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Recursion: the essentials
When to reach for it
The problem is defined by a smaller copy of itself: nested structure (3[a2[c]]), a value given by a recurrence (Fibonacci, powers), a number reduced by a fixed step (is n a power of three? Divide by 3 and ask again), a choice repeated at every position. If you can say "the answer for n is built from the answer for something smaller", that sentence is the function.
The pattern
Trust the recursive call: assume it returns the right answer for the smaller input and write only how to build this answer from it. Then check that the base case catches every input the step can reach — including 0, 1, the empty input and negatives. If the same arguments come back again and again, memoise.
def power(x, n): # x to the n, n >= 0, in O(log n) calls
if n == 0:
return 1
half = power(x, n // 2)
return half * half if n % 2 == 0 else half * half * x
Cost
Time is the number of calls times the work per call. Space is the maximum depth, since every pending call holds a stack frame. Naive Fibonacci makes O(φⁿ) calls, about 1.6ⁿ; memoised, it makes O(n).
Common mistakes
- A base case some inputs step past:
n == 0when n can be negative, or a step of 2 that jumps over it. - Making the same call twice, as in
power(x, n // 2) * power(x, n // 2), which turns O(log n) calls into O(n). - Running out of stack: Python stops at 1,000 frames by default, so recursion over a 10⁵-long input needs a loop or an explicit stack.
- Slicing or concatenating at every level, a hidden O(n) per call.
Start with
- Power of Three: one step towards the base case.
- Fibonacci Number: two calls, and why memoising matters.
- Decode String: recursion that mirrors the nesting.
All recursion problems
Easy (9)
- Palindrome Linked List Linked List, Two Pointers, Stack
- Reverse Linked List Linked List
- Remove Linked List Elements Linked List
- Merge Two Sorted Lists Linked List, Two Pointers
- Check if Two Trees are Isomorphic Tree, Depth-First Search
- Transform to Sum Tree Tree, Depth-First Search
- Power of Four Math, Bit Manipulation
- Fibonacci Number Math, Dynamic Programming
- Power of Three Math
Medium (19)
- Add 1 to a Number Represented as Linked List Linked List, Math
- Remove Nodes From Linked List Linked List, Stack, Monotonic Stack
- Reorder List Linked List, Two Pointers, Stack
- Convert Sorted List to Binary Search Tree Linked List, Tree, Divide and Conquer
- Swap Nodes in Pairs Linked List
- Add Two Numbers Linked List, Math
- Foldable Binary Tree Tree, Depth-First Search
- Sum Tree Tree, Depth-First Search
- Trim a Binary Search Tree Tree, Depth-First Search
- Delete Node in a BST Tree, Binary Search
- Count Collisions of Monkeys on a Polygon Math
- Minimum Non-Zero Product of the Array Elements Math, Greedy
- Count Good Numbers Math
- Elimination Game Math
- Different Ways to Add Parentheses Math, String, Memoization
- Find Kth Bit in Nth Binary String String, Simulation
- Find the Winner of the Circular Game Array, Math, Simulation
- Predict the Winner Array, Dynamic Programming, Game Theory
- Decode String String, Stack
Hard (12)
- Reverse Nodes in k-Group Linked List
- Maximum Path Sum Between Two Leaves Tree, Depth-First Search
- Maximum Sum BST in Binary Tree Tree, Depth-First Search, Dynamic Programming
- Binary Tree Maximum Path Sum Tree, Depth-First Search, Dynamic Programming
- Permutation Sequence Math
- Tiling a Rectangle with the Fewest Squares Backtracking
- Basic Calculator Math, String, Stack
- Parsing A Boolean Expression String, Stack
- Integer to English Words String, Math
- Special Binary String String, Divide and Conquer, Greedy
- Number of Digit One Math, Digit DP
- Regular Expression Matching String, Dynamic Programming
Companies that ask recursion problems
- Amazon 38 problems on recursion
- Microsoft 26 problems on recursion
- Google 17 problems on recursion
- Meta 9 problems on recursion
- Adobe 6 problems on recursion
- Bloomberg 6 problems on recursion
- Apple 3 problems on recursion
- Hulu 2 problems on recursion
- Yahoo 2 problems on recursion
- Yelp 2 problems on recursion
- Accenture 1 problem on recursion
- Airbnb 1 problem on recursion
Next topic: Merge Sort