Recursion Questions —
Every classic, with a call stack to watch.
Recursion questions test something more specific than "can you write a recursive function" — they test whether you can identify the base case, the recursive case, and reason about space complexity, under pressure. Every problem below links to a LearnBug walkthrough where you can watch the actual call stack build and unwind.
What are interviewers actually checking for?
Beyond "does it produce the right output," recursion questions check whether you can identify the base case, verify the recursive case makes progress toward it, and explain the space cost — since every recursive call adds a stack frame, something an equivalent iterative solution wouldn't need.
Why visualization helps
Talking through "the call stack builds up, then unwinds" is one thing; watching it actually happen, frame by frame, on a concrete example is what makes it intuitive enough to explain confidently live. LearnBug's recursion lessons all show the stack directly.
Three things to verify in every recursive solution
Is there a base case, and is it reachable?
State it explicitly before coding — "the base case is n == 0" — and confirm every recursive call moves strictly closer to it.
What's the space complexity, not just time?
Every recursive call adds a stack frame — a solution with O(n) time recursion also has O(n) space, which an equivalent iterative version might avoid.
Are there overlapping subproblems?
If the same smaller input recurs across branches (like Fibonacci), mention memoization before being asked — it's often the exact follow-up.
The 8 classic questions
Factorial — the entry point
factorial(n) = n * factorial(n-1), base case factorial(1) = 1. Almost always the first recursion question asked, specifically to check you understand that the multiplication happens on the way back up the stack, not on the way down. Full walkthrough →
Fibonacci — naive vs memoized
The classic overlapping-subproblems example. Expect a direct follow-up: "what's the time complexity, and can you improve it?" — the answer is O(2ⁿ) naive, O(n) with memoization, and this transition is one of the most commonly tested DP intuitions. Full walkthrough →
Reverse a string or linked list recursively
For a string: reverse(s) = reverse(s[1:]) + s[0], base case an empty string. For a linked list, reverse the rest first, then fix the current node's pointers on the way back up — this tests whether you can reason about mutation happening during the unwind phase.
Check if a string is a palindrome recursively
Compare the first and last characters; if they match, recurse on the substring with both ends removed. Base case: a string of length 0 or 1 is always a palindrome. This tests handling two "ends" moving inward, a pattern that generalizes to two-pointer problems.
Tree height / maximum depth
height(node) = 1 + max(height(left), height(right)), base case a null node returns -1 (or 0, depending on convention — state your convention explicitly). This is the foundational recursive tree problem almost every other tree question builds on. Full walkthrough →
Generate all subsets or permutations (backtracking)
Choose an element, recurse, then undo the choice before trying the next one. This is the pattern behind subsets, permutations, N-Queens, and combination-sum — interviewers often test whether you know the choose/explore/un-choose shape by heart. Full walkthrough →
Tower of Hanoi
Move n-1 disks out of the way, move the largest disk, move n-1 disks back. Less about coding difficulty and more about whether you can derive and explain the recurrence T(n) = 2·T(n-1) + 1, and recognize it as O(2ⁿ). Full walkthrough →
Merge sort — recursion powering a real algorithm
Split the array, recursively sort each half, merge. This tests whether you can apply the recursive divide-and-conquer pattern to something more substantial than a toy problem, and correctly derive O(n log n) from the recurrence T(n) = 2·T(n/2) + O(n). Full walkthrough →
Quick Reference
Watch the call stack for every one of these
Paste any recursive function into LearnBug and see every frame push and pop.