Autocoder

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.

Questions11, easy to hard
LanguagesPython and Java
PatternsMemoisation, 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.

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.

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Recursion interview questions with worked solutions: questions with worked answers

  1. 1

    Compute the nth Fibonacci number efficiently with memoisation.

    easy

    The 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.

    python
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def fib(n):
        if n < 2:
            return n
        return fib(n - 1) + fib(n - 2)
    java
    import 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. 2

    Reverse an array of characters in place using recursion.

    easy

    Swap 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.

    python
    def 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)
    java
    import 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. 3

    Maximum depth of a binary tree.

    easy

    The 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).

    python
    def max_depth(root):
        if not root:
            return 0
        return 1 + max(max_depth(root.left), max_depth(root.right))
    java
    import 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. 4

    Compute x raised to the power n quickly (fast exponentiation).

    medium

    Use 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.

    python
    def 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)
    java
    import 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. 5

    Tower of Hanoi: list the moves to transfer n disks from one peg to another.

    medium

    To 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.

    python
    def 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 moves
    java
    import 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. 6

    Flood fill: recolour a connected region of a grid starting from a pixel.

    medium

    Remember 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.

    python
    def 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 img
    java
    import 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. 7

    Validate a binary search tree.

    medium

    Checking 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).

    python
    def 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))
    java
    import 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. 8

    Lowest common ancestor of two nodes in a binary tree.

    medium

    Recurse 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.

    python
    def 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 right
    java
    import 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. 9

    Josephus problem: n people stand in a circle and every kth person is removed. Who survives?

    hard

    Let 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.

    python
    def josephus(n, k):
        if n == 1:
            return 0
        return (josephus(n - 1, k) + k) % n
    
    # 1-based survivor: josephus(n, k) + 1
    java
    import 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. 10

    Different ways to add parentheses: all results of evaluating an expression like 2*3-4*5.

    hard

    Divide 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.

    python
    def 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 res
    java
    import 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. 11

    Why does recursion cause a stack overflow, and how do you avoid it?

    medium

    Each 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

See all in this section