Recursion interview questions with worked solutions
Last updated 2026-11-19
Recursion solves a problem by solving smaller copies of it. Every correct recursive function has three parts: a base case that stops the recursion, a recursive step that moves towards the base case, and a clear statement of what the function returns for its input. If you can say that last sentence in plain words, the code usually follows.
The questions below start with memoisation and simple reductions, then move through trees, grids and divide and conquer. The backtracking family (subsets, permutations, N-Queens) has its own page: backtracking questions. Dynamic programming is recursion plus caching, covered in dynamic programming questions. General test guidance is in the DSA coding round guide.
| Questions | 11, easy to hard |
|---|---|
| Languages | Python and Java |
| Patterns | Memoisation, divide and conquer, tree recursion |
How to design a recursive solution
First write the contract: "depth(node) returns the number of nodes on the longest path from node down to a leaf". Then handle the smallest input (the base case), then assume the function already works on smaller inputs and combine their results.
Count the cost by drawing the recursion tree: the number of nodes is the number of calls, and the work per node adds up. Fibonacci without caching has an exponential tree; with caching it collapses to linear.
- One call per step: linear recursion (factorial, reverse string).
- Two calls per step with overlap: memoise (Fibonacci).
- Two calls on halves of the input: divide and conquer (fast power, merge sort).
- One call per child: tree and grid traversal.
Stack depth and limits
Each call uses stack space, so recursion depth is part of the space complexity. Python raises RecursionError at about a thousand frames by default, and Java throws StackOverflowError somewhere past a few thousand to tens of thousands depending on frame size. For deep inputs, convert to an explicit stack or a loop.
Tree node used in the tree questions
The tree problems assume a binary tree node with a value and left and right children.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = rightclass TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}Recursion interview questions with worked solutions: questions with worked answers
1 Compute the nth Fibonacci number efficiently with memoisation.
easyThe plain recursion fib(n-1) + fib(n-2) recomputes the same values and takes exponential time. Cache each result the first time it is computed so every n is solved once. In Python functools.lru_cache does this in one line; in Java keep a long array. An iterative two-variable version uses O(1) space. Time O(n), space O(n) for the cache and the recursion depth.. Edge cases: n = 0 and 1 (base cases), large n overflowing 64-bit (n > 92), negative input.
pythonfrom functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)javaimport java.util.*; class Solution { static long[] memo = new long[93]; static long fib(int n) { if (n < 2) return n; if (memo[n] != 0) return memo[n]; return memo[n] = fib(n - 1) + fib(n - 2); } }2 Reverse an array of characters in place using recursion.
easySwap the two ends, then recurse on the inner range. The base case is when the left index meets or passes the right index. Working with indices avoids copying a new substring at every level, which would make the solution O(n^2). Time O(n), space O(n) for the recursion depth.. Edge cases: empty array, one character, even and odd lengths.
pythondef reverse(a, l=0, r=None): if r is None: r = len(a) - 1 if l >= r: return a[l], a[r] = a[r], a[l] reverse(a, l + 1, r - 1)javaimport java.util.*; class Solution { static void reverse(char[] a, int l, int r) { if (l >= r) return; char t = a[l]; a[l] = a[r]; a[r] = t; reverse(a, l + 1, r - 1); } }3 Maximum depth of a binary tree.
easyThe contract: depth(node) is the number of nodes on the longest root-to-leaf path in that subtree. An empty tree has depth 0; otherwise it is 1 plus the larger of the two child depths. This post-order pattern, combine the answers of the children, solves a huge number of tree questions. Time O(n), space O(h) for tree height h (O(n) for a skewed tree).. Edge cases: empty tree, a single node, a skewed tree (deep recursion).
pythondef max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right))javaimport java.util.*; class Solution { static int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } }4 Compute x raised to the power n quickly (fast exponentiation).
mediumUse the identity x^n = (x^(n/2))^2, times x if n is odd. Compute the half power once, store it, and square it. That halves n each call, so only about log n multiplications are needed. Handle a negative exponent by inverting x and negating n; in Java use a long for n because -Integer.MIN_VALUE overflows int. Time O(log n), space O(log n).. Edge cases: n = 0 (return 1), negative n, x = 0 or 1 or -1, n = Integer.MIN_VALUE.
pythondef my_pow(x, n): if n < 0: x, n = 1 / x, -n def go(n): if n == 0: return 1.0 half = go(n // 2) return half * half if n % 2 == 0 else half * half * x return go(n)javaimport java.util.*; class Solution { static double myPow(double x, int n) { long m = n; if (m < 0) { x = 1 / x; m = -m; } return go(x, m); } static double go(double x, long n) { if (n == 0) return 1.0; double half = go(x, n / 2); return n % 2 == 0 ? half * half : half * half * x; } }5 Tower of Hanoi: list the moves to transfer n disks from one peg to another.
mediumTo move n disks from source to target using a spare peg: move n - 1 disks to the spare peg, move the largest disk to the target, then move the n - 1 disks from the spare onto the target. The base case is zero disks. The number of moves is 2^n - 1, which is also the minimum. Time O(2^n) time, space O(n) for recursion.. Edge cases: n = 0 (no moves), n = 1 (one move), large n produces an enormous list.
pythondef hanoi(n, src, dst, aux, moves=None): if moves is None: moves = [] if n == 0: return moves hanoi(n - 1, src, aux, dst, moves) moves.append((src, dst)) hanoi(n - 1, aux, dst, src, moves) return movesjavaimport java.util.*; class Solution { static void hanoi(int n, char src, char dst, char aux, List<String> moves) { if (n == 0) return; hanoi(n - 1, src, aux, dst, moves); moves.add(src + "->" + dst); hanoi(n - 1, aux, dst, src, moves); } }6 Flood fill: recolour a connected region of a grid starting from a pixel.
mediumRemember the original colour of the start pixel. If it already equals the new colour, return at once (otherwise the recursion would never stop). Otherwise recolour the pixel and recurse into the four neighbours that still have the original colour. Recolouring doubles as the visited marker. Time O(rows * cols), space O(rows * cols) for recursion in the worst case.. Edge cases: new colour equal to old colour, a one-pixel region, a region touching the borders.
pythondef flood_fill(img, sr, sc, color): old = img[sr][sc] if old == color: return img def dfs(r, c): if r < 0 or c < 0 or r >= len(img) or c >= len(img[0]) or img[r][c] != old: return img[r][c] = color dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) dfs(sr, sc) return imgjavaimport java.util.*; class Solution { static int[][] floodFill(int[][] img, int sr, int sc, int color) { int old = img[sr][sc]; if (old != color) dfs(img, sr, sc, old, color); return img; } static void dfs(int[][] img, int r, int c, int old, int color) { if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return; img[r][c] = color; dfs(img, r + 1, c, old, color); dfs(img, r - 1, c, old, color); dfs(img, r, c + 1, old, color); dfs(img, r, c - 1, old, color); } }7 Validate a binary search tree.
mediumChecking only a node against its children is wrong: every node in the left subtree must be smaller than the root, not just the left child. Pass down an allowed range (low, high) and narrow it: the left child gets high = node.val, the right child low = node.val. A node outside its range makes the tree invalid. Use strict inequalities when duplicates are not allowed. Time O(n), space O(h).. Edge cases: a single node, duplicates, node values at Integer.MIN or MAX (use null or long bounds).
pythondef is_valid_bst(root, low=None, high=None): if not root: return True if low is not None and root.val <= low: return False if high is not None and root.val >= high: return False return (is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high))javaimport java.util.*; class Solution { static boolean isValidBST(TreeNode root) { return check(root, Long.MIN_VALUE, Long.MAX_VALUE); } static boolean check(TreeNode n, long low, long high) { if (n == null) return true; if (n.val <= low || n.val >= high) return false; return check(n.left, low, n.val) && check(n.right, n.val, high); } }8 Lowest common ancestor of two nodes in a binary tree.
mediumRecurse into both subtrees. If the current node is null or is one of the targets, return it. If both sides return a non-null node, the targets sit on different sides, so the current node is the answer. Otherwise return whichever side was non-null. This assumes both nodes exist in the tree. Time O(n), space O(h).. Edge cases: one node is an ancestor of the other, the same node given twice, a skewed tree.
pythondef lowest_common_ancestor(root, p, q): if not root or root is p or root is q: return root left = lowest_common_ancestor(root.left, p, q) right = lowest_common_ancestor(root.right, p, q) if left and right: return root return left or rightjavaimport java.util.*; class Solution { static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; return left != null ? left : right; } }9 Josephus problem: n people stand in a circle and every kth person is removed. Who survives?
hardLet f(n, k) be the 0-based position of the survivor. With one person it is 0. After the first removal, n - 1 people remain and counting restarts from the person after the removed one, so positions shift by k: f(n, k) = (f(n - 1, k) + k) mod n. Add 1 for a 1-based answer. For n = 7, k = 3 the survivor is person 4. Time O(n), space O(n) recursion (an iterative loop gives O(1)).. Edge cases: k = 1 (the last person survives), n = 1, k larger than n.
pythondef josephus(n, k): if n == 1: return 0 return (josephus(n - 1, k) + k) % n # 1-based survivor: josephus(n, k) + 1javaimport java.util.*; class Solution { static int josephus(int n, int k) { if (n == 1) return 0; return (josephus(n - 1, k) + k) % n; } // 1-based survivor: josephus(n, k) + 1 }10 Different ways to add parentheses: all results of evaluating an expression like 2*3-4*5.
hardDivide and conquer on the operators. For each operator, recursively compute every possible value of the left part and the right part, then combine every pair with that operator. A string with no operator is a single number, which is the base case. For "2*3-4*5" the results are -34, -14, -10, -10 and 10. Memoising by substring avoids recomputing repeated parts. Time exponential in the number of operators (the Catalan number of outcomes), space proportional to the number of results.. Edge cases: a single number, only one operator, multi-digit numbers.
pythondef diff_ways_to_compute(expr): if expr.isdigit(): return [int(expr)] res = [] for i, c in enumerate(expr): if c in "+-*": for a in diff_ways_to_compute(expr[:i]): for b in diff_ways_to_compute(expr[i + 1:]): res.append(a + b if c == '+' else a - b if c == '-' else a * b) return resjavaimport java.util.*; class Solution { static List<Integer> diffWaysToCompute(String expr) { List<Integer> res = new ArrayList<>(); for (int i = 0; i < expr.length(); i++) { char c = expr.charAt(i); if (c == '+' || c == '-' || c == '*') { for (int a : diffWaysToCompute(expr.substring(0, i))) for (int b : diffWaysToCompute(expr.substring(i + 1))) res.add(c == '+' ? a + b : c == '-' ? a - b : a * b); } } if (res.isEmpty()) res.add(Integer.parseInt(expr)); return res; } }11 Why does recursion cause a stack overflow, and how do you avoid it?
mediumEach call adds a frame to the call stack and the stack has a fixed size. A missing or unreachable base case, or simply a very deep input such as a linked list of a million nodes, exhausts it. Fixes: check the base case and that the argument shrinks, convert the recursion to a loop with an explicit stack, use tail-style accumulation where the language optimises it (Python and Java do not), or add memoisation so fewer calls happen.
Frequently asked questions
How do I find the base case?
Ask what the smallest valid input is and what the answer is for it: an empty list, a null node, n = 0 or 1. Then check that every recursive call moves strictly towards it.
What is the difference between recursion and iteration?
Both repeat work. Recursion expresses it as smaller sub-problems and uses the call stack; iteration uses a loop and explicit variables. Anything recursive can be made iterative with a stack.
What is tail recursion and does Python or Java optimise it?
A function whose last action is the recursive call. Languages such as Scheme can reuse the frame. Neither Python nor Java does, so deep tail recursion still overflows.
When should I add memoisation?
When the recursion tree contains the same sub-problem more than once, as in Fibonacci. Cache the answer keyed by the arguments. That is the first step towards dynamic programming.
Where do subsets and permutations belong?
They are recursion with choices that you undo afterwards, which is backtracking. See backtracking questions.
Related guides
More in DSA Interview Questions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions