Recursion and backtracking interview questions, with answers

The questions, with answers

1. 1.What is recursion, and what are the two parts every recursive function must have?

   A function that solves a problem by calling itself on a smaller instance of the same problem. It needs a base case — an input small enough to answer directly, which stops the calls — and a recursive case that reduces the input and combines the result of the smaller call. Miss the base case, or write a recursive case that does not shrink the input, and the calls never end; the program dies with a stack overflow rather than an infinite loop. The discipline interviewers look for: state the base case first, make sure every recursive call moves strictly toward it, and trust the recursive call to be correct for smaller inputs rather than tracing it all the way down in your head.

   int factorial(int n) {
       if (n <= 1) return 1;            // base case
       return n * factorial(n - 1);     // recursive case: strictly smaller input
   }

2. 2.What happens on the call stack during recursion, and why does deep recursion overflow?

   Every call pushes a frame holding its parameters, local variables and the return address; the frame is popped when the call returns. A recursion n levels deep has n frames live at once, so it uses O(n) memory even if each frame is tiny — that is the space complexity people forget to count. The stack is a fixed region (about 512 KB to 1 MB per thread in Java, 8 MB on typical Linux for C, and Python refuses beyond a recursion limit of 1,000 by default), so recursing a million levels overflows it. The fixes are to rewrite iteratively with an explicit stack, to rely on tail-call optimisation in languages that guarantee it (Scheme, Kotlin's tailrec — not Java, not Python), or to bound the depth, as merge sort's log n depth naturally does.

3. 3.When should you use recursion instead of iteration, and vice versa?

   Any recursion can be rewritten as iteration with an explicit stack, and any loop as recursion, so the choice is about clarity and cost. Recursion wins when the problem is naturally self-similar — tree traversals, divide and conquer, permutations, anything on a nested structure — because the code mirrors the structure and the call stack manages the bookkeeping for you. Iteration wins when the recursion would be linear and deep (summing a list, walking a linked list), where the stack frames add memory and overhead for nothing, and when the language does not optimise tail calls. The interview line: recursion for branching problems, iteration for linear ones, and convert when the depth could exceed the stack.

4. 4.Why is the naive recursive Fibonacci exponential, and how does memoisation fix it?

   Because fib(n) calls fib(n-1) and fib(n-2), and those two calls repeat the same sub-problems: fib(n-2) is computed once for fib(n-1) and again for fib(n), and the duplication compounds at every level. The recursion tree has roughly 2^n nodes — 1.6^n more precisely — so fib(50) is about a trillion calls. Memoisation stores each result the first time it is computed, in an array or map keyed by n, and returns the stored value on every repeat; every n is then computed once and the tree collapses to n calls. That is top-down dynamic programming. The bottom-up version fills the array from fib(0) upward with a loop and needs only the last two values, giving O(n) time and O(1) space.

   long[] memo = new long[100];
   long fib(int n) {
       if (n <= 1) return n;
       if (memo[n] != 0) return memo[n];      // already computed
       return memo[n] = fib(n - 1) + fib(n - 2);
   }

5. 5.How do you count the calls a recursive function makes?

   Draw the recursion tree and count its nodes, including the root. For a function that makes one call per level, the count is the depth: factorial(n) makes n calls. For two calls per level with the same decrease, it doubles each level: a function that calls itself twice on n-1 down to a base case makes 2^n - 1 calls. For Fibonacci-style calls on n-1 and n-2, the count follows its own recurrence: calls(n) = 1 + calls(n-1) + calls(n-2), which gives 1, 1, 3, 5, 9, 15 for n = 0 to 5 — so fib(4) makes 9 calls and fib(5) makes 15. A generate-every-subset routine that decides include or exclude for each of k elements reaches 2^k leaves, one per subset. Interviewers ask for the number, then for the general shape; give both.

6. 6.What is backtracking, and what does the standard template look like?

   Backtracking is recursion that builds a candidate solution one choice at a time and undoes a choice as soon as it cannot lead to a valid solution, then tries the next option. The template: if the candidate is complete, record it and return; otherwise, for each available choice, apply it, recurse, and then undo it. The undo is what makes it backtracking rather than plain recursion — the same partial state is reused across branches instead of being copied. Permutations, subsets, combinations that sum to a target, Sudoku, N-Queens and maze paths are all this template with a different notion of "choice" and "valid".

   void permute(List<Integer> path, boolean[] used, int[] a, List<List<Integer>> out) {
       if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }   // complete
       for (int i = 0; i < a.length; i++) {
           if (used[i]) continue;
           used[i] = true;  path.add(a[i]);           // choose
           permute(path, used, a, out);               // explore
           path.remove(path.size() - 1);  used[i] = false;   // un-choose
       }
   }

7. 7.What is pruning, and why does it matter more than the base case in backtracking?

   Pruning is checking a constraint as soon as a partial candidate breaks it and abandoning that branch immediately, rather than finishing the candidate and rejecting it at the end. In N-Queens, placing a queen that attacks an existing one and then continuing to fill the remaining rows is wasted work; checking the attack before recursing cuts the whole subtree. The difference is not a constant factor — generate-and-test explores all n^n placements, while pruned backtracking explores a small fraction of them, which is why 8-Queens finishes instantly with pruning and never without it. A good backtracking answer names the constraint you check early, the order you try choices in (most constrained first often prunes more), and the base case — in that order of importance.

8. 8.How do you generate all subsets of a set, and what is the complexity?

   Decide, for each element in turn, whether to include it or leave it out, and recurse to the next element; when you have decided every element, record the current selection. Each element doubles the number of outcomes, so a set of k elements yields 2^k subsets, including the empty set — 32 for five elements. The time is O(2^k × k) if you copy each subset out, and the recursion depth is only k. The bitmask version is the iterative twin: loop a counter from 0 to 2^k - 1 and let bit i say whether element i is in. For subsets of a fixed size r, add a pruning check that stops when the selection already has r elements or cannot reach r with what remains — a combination generator.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on recursion & backtracking and 60 across DSA.