Recursion Interview Questions: 20 Problems to Practice

Recursion can feel like a loop with no exit until you see where each call stops and what it returns. These recursion interview questions cover 20 problems by pattern, with difficulty cues, solution outlines, and complexity notes to help you practice with purpose.

Table of Contents

• Foundational Recursion Interview Questions
• Array and String Recursion Problems
• Linked List and Tree Recursion Questions
• Backtracking and Divide-and-Conquer Recursion
• Advanced Recursion Questions: Memoization, Complexity, and Debugging
• Frequently Asked Questions About Recursion Interviews
• Conclusion

Foundational Recursion Interview Questions

Recursion is a way to solve a problem by calling the same function on a smaller version of it. Every sound solution has a base case that stops the calls and a recursive case that moves toward that stop.

Start by saying what one call means. For factorial, factorial(n) returns the product from 1 through n. Then define the stopping point: factorial(0) = 1. The recursive rule is n * factorial(n - 1).

1. Find a number’s factorial, Easy

Use the base case n <= 1, which returns 1. Otherwise return n * factorial(n - 1). For factorial(4), the calls reach 1, then unwind as 1 × 2 × 3 × 4. Time is O(n); stack space is O(n).

2. Return the nth Fibonacci number, Easy

Define fib(0) = 0 and fib(1) = 1. For larger n, return fib(n - 1) + fib(n - 2). This direct version takes exponential time because it repeats work, and uses O(n) stack space. Tell the interviewer that caching can reduce the repeated work.

3. Sum an array recursively, Easy

Pass an index into a helper. If it reaches the array length, return 0. Otherwise return the current value plus the sum from the next index. Each value is visited once, so time is O(n) and stack space is O(n). An iterative loop uses O(1) extra space.

4. Search a sorted array with binary search, Medium

Pass left and right bounds. Return failure when left exceeds right. Check the midpoint; if it misses, recurse only into the half that could contain the target. Time is O(log n), with O(log n) stack space. The recursive version is clear, but iteration avoids that stack cost.

Rate each question yourself before practice: easy if the base case is clear, medium if the state or return value takes thought, and hard if you must manage many branches.

Use this call-stack sketch for factorial: factorial(4) → factorial(3) → factorial(2) → factorial(1). The calls pause on the way down. They return results in reverse order.

Array and String Recursion Problems

Array and string problems often use a moving index or two pointers. Before coding, say what the helper has already checked. That simple contract makes the recursive step easier to trust.

5. Reverse a string, Easy

Use two indices, one at each end. If they meet or cross, stop. Swap those characters, then recurse inward. For a mutable character array, the algorithm takes O(n) time and O(n) stack space; the swaps use O(1) extra space besides the call stack.

6. Check whether a string is a palindrome, Easy

Compare the first and last characters. If they differ, return false. If they match, recurse on the inner range. Return true when the pointers meet. This uses O(n) time and O(n) stack space. Clarify whether spaces, case, and punctuation count before you write code.

7. Raise a number to an integer power, Medium

A basic solution multiplies by the base, then recurses with the exponent reduced by one. That takes O(n) time. A stronger version uses exponentiation by squaring: solve the half-sized exponent once, square the result, and handle an odd exponent with one extra multiply. It takes O(log n) time and stack space.

8. Find the first matching index in an array, Easy

Pass the current index. Return -1 when it reaches the end. Return the index if its value matches; otherwise recurse at the next index. The worst case is O(n) time and O(n) stack space. This is a good prompt for comparing a direct recursive scan with a simple loop.

For each problem, ask yourself what changes between calls and what condition ends the search.

For string reversal, the trace on cat is small: swap c with t, then stop at the middle. Naming the range clearly also helps you avoid off-by-one errors on empty and one-character strings.

Linked List and Tree Recursion Questions

Linked lists and trees have recursive structure built in. A list node points to the remaining list; a tree node points to smaller subtrees. The challenge is choosing whether a call should return an answer, pass state down, or do both.

9. Reverse a linked list, Medium

Return the node when the list is empty or has one node. Recursively reverse the rest. Then point the next node back to the current node and clear the current node’s old link. Time is O(n), stack space is O(n). Explain why clearing the old link prevents a cycle.

10. Find a tree’s maximum depth, Easy

Return 0 for an empty node. Otherwise return 1 plus the larger depth of its left and right children. The function visits each node once, so time is O(n). Stack space is O(h), where h is tree height. A balanced tree has less depth than a long, one-sided tree.

11. Print a tree in inorder, Easy

For each node, recurse left, visit the node, then recurse right. The traversal takes O(n) time and O(h) stack space. In a binary search tree, inorder visits values in sorted order. Preorder and postorder use the same calls but move the visit action.

12. Find a root-to-leaf path with a target sum, Medium

Pass the remaining sum down. Subtract the current node’s value before calling its children. At a leaf, succeed only if the remaining sum matches that leaf’s value. Time is O(n); stack space is O(h). If the prompt asks for every matching path, keep a path list and undo each change after returning.

Most tree solutions follow a simple contract: solve the left subtree, solve the right subtree, then combine their answers at the current node. The tree recursion patterns and traversal examples give you more variations to practice, including depth and path-style questions.

When you analyze tree space, use height, not node count, for the active call stack. A skewed tree can make height equal to the number of nodes, which may make an iterative traversal safer for deep input.

Backtracking and Divide-and-Conquer Recursion

Backtracking explores choices and undoes each choice before trying another. Divide and conquer splits one problem into smaller parts, solves those parts, then combines the results. Both use recursion, but their work at each call differs.

13. Generate all subsets, Medium

At each index, either include the value or skip it. When every value has a decision, save a copy of the current subset. There are 2ⁿ subsets, so output alone takes exponential space. The recursion stack is O(n). Copy the path when saving it, or later changes will alter saved results.

14. Generate all permutations, Medium

Build a path one unused value at a time. When its length matches the input, save a copy. For distinct values, there are n! outputs, and writing them costs at least O(n × n!) time. Use a set or a used array to track choices, then undo the choice after the recursive call.

15. Find combinations that reach a target, Medium

Track the remaining target. Add a candidate, recurse, then remove it before trying the next. If values may be reused, pass the same candidate index; if not, advance it. Stop a branch when it cannot reach a valid answer. The runtime depends on how many combinations the input permits.

16. Merge sort an array, Medium

Split the range in half until each piece has one item. Merge the sorted halves by repeatedly taking the smaller front value. The recurrence is T(n) = 2T(n/2) + O(n), giving O(n log n) time. The merge needs O(n) extra space, with O(log n) call-stack depth.

In an interview, describe the state before the code. For subsets, say, “The path contains choices made so far, and the index marks the next choice.” Then name the base case and identify the undo step. That makes a backtracking solution much easier to review.

Advanced Recursion Questions: Memoization, Complexity, and Debugging

Advanced recursion prompts test more than the recurrence. Expect follow-ups about repeated work, memory use, edge cases, or whether a loop would be safer. Separate total calls from the deepest active call chain when you explain complexity.

17. Optimize Fibonacci with memoization, Medium

Keep the same recurrence as the direct solution, but store each result by input value. Before computing fib(n), return the cached result if one exists. Each value is then solved once. Time and cache space are O(n); stack space is also O(n). This is top-down dynamic programming.

18. Traverse a directory tree, Medium

For each directory, inspect its entries. Process files directly and recurse into child directories. Time is O(N) for N entries, assuming each is visited once. Stack space depends on the deepest nested path. If links can point back to an already visited directory, track visited entries to avoid repeated traversal.

19. Count connected regions in a grid, Medium

Scan each cell. When you find unvisited land, start depth-first search and mark each connected land cell before exploring its neighbors. The full scan is O(rows × columns) time. Recursion depth can reach that many cells in a narrow region, so an explicit stack may be safer for large grids.

20. Debug a recursive function that never stops, Easy

Check whether the base case can be reached from every recursive path. Then trace a small input and confirm that each call moves closer to the stopping condition. A missing base case can cause unbounded calls; a base case with the wrong boundary can fail on empty input. Deep but valid recursion can still exhaust the call stack.

For complexity, count how many calls the algorithm makes to estimate time. Then count the maximum calls active at once to estimate stack space. Naive Fibonacci makes exponentially many calls, but its deepest active path is only O(n). Recursive binary search makes O(log n) calls and holds O(log n) stack frames.

Phantom Code AI is an invisible AI desktop assistant for coding interviews that listens, transcribes, recognizes problem types, and provides real-time guidance during mock or live technical interviews. If you use it in a mock, treat its guidance as a prompt to explain the base case and complexity yourself. Check the interview rules before using any assistant in a live session.

Tail recursion can put the recursive call last, but don't assume your language will optimize it. A loop or explicit stack may be the better choice when input depth is large. For an additional way to rehearse your spoken reasoning, Phantom Code AI can be part of mock interview practice rather than a replacement for tracing the solution yourself.

Frequently Asked Questions About Recursion Interviews

What are the main parts of a recursive function?

A recursive function needs a base case and a recursive case. The base case returns an answer without another call. The recursive case makes progress toward that condition, then uses the result. In an interview, state what each call returns before you write code. This makes it easier to spot a stopping condition that can never be reached.

How do I explain recursion in an interview?

Explain the function’s contract in one sentence, then give its base case. Describe how the input gets smaller or simpler with each call. After coding, trace a small example and discuss time and stack space separately. If the depth could grow too large, mention an iterative alternative and why you would choose it.

Is recursion faster than iteration?

Not by default. The answer depends on the algorithm and the language runtime. A recursive tree traversal may express the structure clearly, while a loop can avoid call-stack overhead. For binary search, both approaches take O(log n) time, but iterative binary search uses O(1) extra space instead of O(log n) stack space.

What causes a stack overflow in recursion?

A stack overflow happens when too many function calls remain active at once. A missing or unreachable base case can cause that, but a correct algorithm can also go too deep on large input. Check that each call makes progress. Then compare the maximum recursion depth with the problem’s input size and consider an explicit stack.

Conclusion

Work through the problems in order, and say each function’s contract aloud before you code. Start with factorial, then trace a tree traversal and a backtracking problem by hand. For your next practice session, pick one problem you missed and rewrite its base case and complexity analysis from memory.