Recursion and Backtracking Questions

Recursion mechanics (base and recursive cases, tracing call stack frames, what lives on the stack versus the heap, tail calls, recursion depth limits and stack overflow diagnosis, recursion-to-iteration conversion with an explicit stack or trampoline, recursion versus iteration trade-offs) and recursion on nested data and simple divide-and-conquer (Euclid's gcd, string reversal, flattening nested lists and dictionaries lazily with generators, recursive maximum subarray). Also backtracking search over combinatorial spaces: permutations (including duplicates and the k-th permutation), subsets, combinations, combination sum, generating balanced parentheses, N-Queens (with bitmasks and symmetry), Sudoku (with minimum-remaining-values ordering), word search, palindrome partitioning, Knight's Tour and Hamiltonian paths. Covers the choose/explore/undo template, how it differs from plain DFS, state-leakage bugs, pruning, and recursion-tree complexity (O(b^d)) including call-tree counts. Memoized recursion, tree traversals, and general graph search are covered elsewhere.

MediumTechnical
45 practiced

You are implementing binary tree traversals in a codebase that must handle very deep trees (depth over 10,000). Decide between recursion and an iterative stack-based approach, weighing stack overflow risk, readability, maintainability, and performance, and justify the choice.

EasyTechnical
45 practiced

Implement a recursive function that returns all permutations of a list of distinct integers without using library permutation helpers. Show the output for [1, 2, 3], explain how you avoid shared-state bugs, and state the time and space complexity.

EasyTechnical
43 practiced

Implement the Euclidean algorithm recursively to compute gcd(a, b). Explain the base case, handle zero and negative inputs, and analyze the running time. Example: gcd(48, 18) is 6.

EasyTechnical
42 practiced

Write factorial(n) twice in Python, once recursively and once iteratively. Compare time and space for both, and explain whether tail-call optimization would change the recursive version's space and why Python does not do it.

MediumTechnical
40 practiced

Implement backtracking in Python for the Combination Sum variant where the candidate list may contain duplicates and each number may be used at most once: return unique combinations that reach the target. Explain how you avoid duplicate combinations.

Unlock Full Question Bank

Get access to all 33 Recursion and Backtracking interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.