Skip to content
notes.vinhnq.com

Search

Data Structures & AlgorithmsMid21 min read

Recursion, binary search and a few classic algorithms

Review 19 cards
On this page

Basic algorithms series: 1. Big-O and O(n²) sorts · 2. Recursion and binary search · 3. Merge sort and quicksort

This post shows how to write correct recursion (base case, recurrence), when it overflows the JVM stack, and how memoization speeds it up. Then come linear and binary search with the overflow bug in mid, and three interview classics: primality, Fibonacci, palindromes. Read part 1 first to get comfortable with Big-O; the recursion here is the foundation for merge sort and quicksort in part 3.

1. Recursion

Key idea: a recursive function calls itself on a smaller input until it hits the base case, then combines the results on the way back up. Every level costs a stack frame, so depth decides whether it’s safe in Java.

1.1. What it is

Recursion is when a function calls itself on a smaller input. A correct recursive function needs two things:

  1. A base case: the smallest case with an immediate answer and no further calls. This is the stopping condition.
  2. A recurrence: a way to express the problem through smaller subproblems, where every call moves closer to the base case. Otherwise the recursion never ends.

1.2. How to solve a problem recursively

  1. Define the function f: what it takes and what it returns.
  2. Identify the base case.
  3. Find the recurrence: split the problem into subproblems closer to the base case.
  4. Combine the subproblem results into the answer for the bigger problem.

1.3. Case study: factorial

0! = 1, and n! = n · (n-1)! for n > 0. The base case is n == 0; the subproblem is identical to the original, just with a smaller argument.

static long factorial(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be >= 0");
    if (n == 0) return 1;                 // base case
    return n * factorial(n - 1);          // recurrence
}

I use long because int overflows already at 13!; long only goes up to 20!, beyond that you need BigInteger.

factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1 * factorial(0)   <- base case
             = 4 * 3 * 2 * 1 * 1
             = 24

On the JVM, each call creates a new stack frame (a block of memory holding the arguments, local variables and return address). Frames pile up until the base case and then unwind one by one:

sequenceDiagram
  participant M as main
  participant F4 as factorial(4)
  participant F3 as factorial(3)
  participant F2 as factorial(2)
  participant F1 as factorial(1)
  participant F0 as factorial(0)
  M->>F4: call
  F4->>F3: call
  F3->>F2: call
  F2->>F1: call
  F1->>F0: call
  F0-->>F1: 1
  F1-->>F2: 1
  F2-->>F3: 2
  F3-->>F4: 6
  F4-->>M: 24

1.4. Properties of recursion

Every recursive method has a branch (if-else, switch) separating the base case from the recursive case, one or more base cases, and calls that make the problem smaller each time.

1.5. Recursion and the JVM call stack (the senior view)

1.6. Memoization

1.7. Live coding: Fibonacci and Pascal’s triangle

The slides suggest two LeetCode problems for practice:

  • “Fibonacci Number”: given n, return F(n) (F(0) = 0, F(1) = 1). The solution is in section 3.2.
  • “Pascal’s Triangle”: generate the first numRows rows of Pascal’s triangle. Every row starts and ends with 1, and each inner number is the sum of the two directly above it. Both the iterative and recursive versions are O(numRows²), exactly the number of values to produce.
Pascal’s Triangle solutions: iterative and recursive
static List<List<Integer>> generate(int numRows) {
    List<List<Integer>> rows = new ArrayList<>();
    for (int r = 0; r < numRows; r++) {
        List<Integer> row = new ArrayList<>(r + 1);
        for (int c = 0; c <= r; c++) {
            if (c == 0 || c == r) row.add(1);
            else row.add(rows.get(r - 1).get(c - 1) + rows.get(r - 1).get(c));
        }
        rows.add(row);
    }
    return rows;   // generate(5) = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
}

A recursive version for a single row: the base case is row 0 = [1], and row r is built from row r - 1.

static List<Integer> pascalRow(int r) {
    if (r == 0) return List.of(1);
    List<Integer> prev = pascalRow(r - 1);
    List<Integer> row = new ArrayList<>(r + 1);
    row.add(1);
    for (int c = 1; c < r; c++) row.add(prev.get(c - 1) + prev.get(c));
    row.add(1);
    return row;
}

2. Searching an array

Key idea: linear search is O(n) and works on any data; binary search is O(log n), needs a sorted array and drops half the range each step. The classic trap is an overflow when computing mid.

Compare the key with each element in turn; return the index on a match, or -1 at the end.

static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == key) return i;
    return -1;
}

Precondition: the array is sorted (say ascending). Compare key with the middle element: smaller means search the left half, larger means the right half, equal means stop. Three variables low, high, mid mark the start, end and middle of the current range. The range halves each step, so it’s O(log n): a million elements take about 20 comparisons.

Picture it: looking up a word in a paper dictionary, you open the middle and throw away the half that can’t contain it.

flowchart TD
  S["low = 0, high = n - 1"] --> C{"low <= high?"}
  C -- "no" --> NF["not found"]
  C -- "yes" --> M["mid = (low + high) >>> 1"]
  M --> Q{"compare a[mid] with key"}
  Q -- "a[mid] < key" --> R["low = mid + 1"] --> C
  Q -- "a[mid] > key" --> L["high = mid - 1"] --> C
  Q -- "equal" --> F["return mid"]

A worked trace (the slides’ example): search for key = 11 in [2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79] (13 elements).

Step low high mid a[mid] Decision
1 0 12 6 50 50 > 11, drop the right half: high = 5
2 0 5 2 7 7 < 11, drop the left half: low = 3
3 3 5 4 11 equal, return index 4

Three comparisons, where linear search needs five (indices 0 to 4). The maximum is ⌊log₂ n⌋ + 1 steps: 4 for 13 elements, 20 for a million.

The iterative version (prefer this in practice; no stack usage):

static int binarySearch(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        if (a[mid] < key) low = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else return mid;
    }
    return -(low + 1);   // like the JDK: encode the insertion point
}

The recursive version (O(log n) depth, the base case is an empty range):

static int binarySearch(int[] a, int key, int low, int high) {
    if (low > high) return -1;                       // base case: empty range
    int mid = low + (high - low) / 2;
    if (key < a[mid]) return binarySearch(a, key, low, mid - 1);
    if (key > a[mid]) return binarySearch(a, key, mid + 1, high);
    return mid;
}
// call: binarySearch(a, key, 0, a.length - 1)

The standard library:

  • Arrays.binarySearch(a, key) and Collections.binarySearch(list, key) return the index when found, and -(insertionPoint) - 1 otherwise, so you also learn where to insert to keep the order.
  • With duplicates, the JDK doesn’t promise which one you get. If you need the first, write a lower bound:
// smallest index i with a[i] >= key (a.length if there is none)
static int lowerBound(int[] a, int key) {
    int lo = 0, hi = a.length;           // half-open [lo, hi)
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
  • Collections.binarySearch on a LinkedList still works, but reaching mid means walking the list, so it degrades to O(n).

3. A few common algorithms

Key idea: all three classics have a “straight from the definition” version in the slides that is slow or buggy. The better versions: trial division up to √n, Fibonacci with a two-variable loop, palindromes with two pointers.

3.1. Primality test

A prime is a natural number greater than 1 divisible only by 1 and itself. The slides try every i from 2 to n - 1, which is O(n). You only need to go up to √n: if n = a · b with a ≤ b, then a ≤ √n. Skipping even numbers halves the work again.

static boolean isPrime(int n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (int i = 3; (long) i * i <= n; i += 2)   // widen to long so i*i can't overflow
        if (n % i == 0) return false;
    return true;
}

O(√n): for n = 2,147,483,647 (the largest prime that fits in an int), the slides’ version does about 2 billion divisions, this one about 23 thousand. To test many numbers in a range, use the Sieve of Eratosthenes, O(n log log n).

3.2. The n-th Fibonacci number

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Naive recursion translates the definition directly, but it’s very slow:

static long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

The call tree shows F(3), F(2) and friends being computed over and over:

flowchart TD
  F5["F(5)"] --> F4["F(4)"]
  F5 --> F3a["F(3)"]
  F4 --> F3b["F(3)"]
  F4 --> F2a["F(2)"]
  F3a --> F2b["F(2)"]
  F3a --> F1a["F(1)"]
  F3b --> F2c["F(2)"]
  F3b --> F1b["F(1)"]

The number of calls grows exponentially, roughly O(1.618ⁿ) (usually just called O(2ⁿ)); fibNaive(50) takes minutes. Memoized recursion computes each F(k) once: O(n) time, O(n) memory.

static long fibMemo(int n, Map<Integer, Long> memo) {
    if (n <= 1) return n;
    Long cached = memo.get(n);
    if (cached != null) return cached;
    long value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, value);
    return value;
}

There’s also an O(log n) approach using matrix exponentiation or “fast doubling”, a favorite in harder rounds.

3.3. Palindrome check

A palindrome reads the same forwards and backwards, like "radar" or "level".

static boolean isPalindrome(String s, int i, int j) {
    if (i >= j) return true;                     // pointers met: empty or one char left
    if (s.charAt(i) != s.charAt(j)) return false;
    return isPalindrome(s, i + 1, j - 1);
}
// call: isPalindrome(s, 0, s.length() - 1)

The slides’ loop version walks the whole string, comparing every pair twice; going to the middle is enough:

static boolean isPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--)
        if (s.charAt(i) != s.charAt(j)) return false;
    return true;
}

The loop is O(n) time, O(1) memory. The recursive version is also O(n) time but uses O(n) stack, so a string of a few hundred thousand characters can trigger a StackOverflowError. A common follow-up: ignore non-alphanumeric characters and compare case-insensitively.

Interactive visualisations

Key idea: watch the step-by-step animations (from Y. Daniel Liang’s textbook) and try keys that are and aren’t in the array.

Exercises

Exercise 1: Four basic recursion problems

Task: using recursion, (a) print a string n times, (b) compute 2ⁿ, (c) compute xⁿ, (d) compute 1 + 2 + ... + n.

Solution to Exercise 1: code and notes on each part
// (a) base case: n <= 0 prints nothing
static void printTimes(String s, int n) {
    if (n <= 0) return;
    System.out.print(s);
    printTimes(s, n - 1);
}

// (b) 2^n = 2 * 2^(n-1), 2^0 = 1. O(n)
static long powerOfTwo(int n) {
    if (n == 0) return 1;
    return 2 * powerOfTwo(n - 1);
}

// (c) halve the exponent: x^n = (x^(n/2))^2, times x if n is odd. O(log n)
static long pow(long x, int n) {
    if (n == 0) return 1;
    long half = pow(x, n / 2);            // call ONCE and reuse
    return (n % 2 == 0) ? half * half : half * half * x;
}

// (d) sum(n) = n + sum(n-1), sum(0) = 0. O(n) time and O(n) stack
static long sumTo(int n) {
    if (n <= 0) return 0;
    return n + sumTo(n - 1);
}
  • For (b), real code just writes 1L << n (valid for n from 0 to 62).
  • (c) is exponentiation by squaring: the recursion is only log₂ n deep. The usual mistake is pow(x, n/2) * pow(x, n/2): calling it twice brings you back to O(n). For negative n, return 1.0 / pow(x, -n) with double, and watch out for n = Integer.MIN_VALUE, because -n is still negative.
  • (d) has the closed form n(n+1)/2, O(1). Recursing with n = 100,000 can cause a StackOverflowError. A nice line for an interview: “recursion is good for practicing the thinking, but in production I’d use the formula or a loop.”

Exercise 2: A three-term recurrence, compute f(1000)

From the course whiteboard: f(1) = 3, f(2) = 7, f(3) = 4, and f(n) = f(n-1) + f(n-2) + f(n-3). For example f(4) = 3 + 7 + 4 = 14. What is f(1000)?

Solution to Exercise 2: analysis, BigInteger and a modulo version
  • Naive recursion branches three ways per level, about O(1.84ⁿ) calls: at n = 1000 it would never finish.
  • Memoization brings it to O(n); a recursion depth of 1000 is fine on the JVM.
  • Best: a loop keeping the last three values, O(n) time and O(1) memory.
  • f(1000) has 265 digits (I ran it to check), overflowing long very early, so you need BigInteger. If the problem asks for the result modulo 10⁹ + 7, use long and reduce at each step.
static BigInteger f(int n) {
    if (n < 1) throw new IllegalArgumentException("n must be >= 1");
    BigInteger a = BigInteger.valueOf(3), b = BigInteger.valueOf(7), c = BigInteger.valueOf(4);
    if (n == 1) return a;
    if (n == 2) return b;
    if (n == 3) return c;
    for (int i = 4; i <= n; i++) {
        BigInteger next = a.add(b).add(c);
        a = b; b = c; c = next;
    }
    return c;
}

static long fMod(int n, long mod) {
    long a = 3, b = 7, c = 4;
    if (n == 1) return a;
    if (n == 2) return b;
    if (n == 3) return c;
    for (int i = 4; i <= n; i++) {
        long next = (a + b + c) % mod;   // a, b, c < mod, so the sum can't overflow a long
        a = b; b = c; c = next;
    }
    return c;
}
// fMod(1000, 1_000_000_007L) = 716358599, matching f(1000).mod(10^9 + 7)

Remember

  • Explain the base case and the recurrence, and why missing either one makes recursion infinite.
  • Know when recursion is safe in Java (O(log n) depth) and when to switch to a loop or an ArrayDeque.
  • Write a binary search that can’t overflow, and explain the JDK’s -(insertionPoint) - 1 return value.
  • Explain why naive Fibonacci is exponential and how memoization brings it to O(n).
  • Remember the overflow limits: int overflows from 13! and F(47), long only holds up to 20! and F(92).

Interview questions

Junior

What’s a base case, and what happens without one?

It’s the smallest case that returns an answer directly without recursing. Without it the JVM throws StackOverflowError.

Without a base case, or if calls don’t move toward it, the recursion never ends until the stack fills up.

Mid

What’s the complexity of naive recursive Fibonacci, and how do you improve it?

About O(φⁿ) with φ ≈ 1.618 (commonly called O(2ⁿ)) because subproblems are recomputed; memoization brings it to O(n).

Bottom-up DP is also O(n) time; keeping just two variables makes memory O(1). Matrix exponentiation or fast doubling gives O(log n).

What’s wrong with mid = (low + high) / 2?

Integer overflow when low + high > Integer.MAX_VALUE, which produces a negative index.

Fix it with low + (high - low) / 2 or (low + high) >>> 1. The JDK had exactly this bug in Arrays.binarySearch.

How do you count the space complexity of a recursive function?

Add the call stack depth: depth d costs O(d), on top of any memory you explicitly allocate.

Recursive factorial(n) is O(n) space even though it creates no arrays; recursive binary search is O(log n); the iterative versions are O(1).

What does Arrays.binarySearch return when the key isn’t found?

-(insertionPoint) - 1, where insertionPoint is where the key would go to keep the array sorted.

It’s always negative when not found, even when insertionPoint is 0, so check >= 0 to know whether it was found. With duplicates, there’s no guarantee which match you get.

Senior

Does Java optimize tail calls? What does that mean for recursive code?

No. Tail recursion still costs O(n) stack, so linearly deep recursion has to be rewritten as a loop.

The JVM keeps full stack frames (partly for stack traces and the security model). Recursion whose depth grows linearly with the input (long lists, degenerate trees, DFS on large graphs) can throw StackOverflowError in production; rewrite it as a loop or use an ArrayDeque as an explicit stack on the heap. Bumping -Xss is only a patch.

Is it OK to catch StackOverflowError and carry on?

Generally no: it’s an Error, signaling a state the application shouldn’t try to recover from.

By the time you catch it the stack is nearly exhausted, so anything in the catch block (logging, allocation) can fail again, and invariants (locks, half-finished state) may already be broken. The right fix is to bound the input depth or rewrite it without recursion.

An API has to check whether lots of numbers are prime. How would you design it?

It depends on the range: a precomputed Sieve of Eratosthenes for small numbers, deterministic Miller-Rabin for numbers up to 64 bits.

  • Small numbers (≤ 10⁷) queried often: build the sieve once at startup (a ~1.25 MB bitset), then each query is O(1).
  • Up to 64 bits: deterministic Miller-Rabin with a fixed set of bases, or BigInteger.isProbablePrime.
  • Trial division up to √n only makes sense for a few small numbers.
  • Spell out the trade-off between memory, startup time and per-request latency.

Useful phrases for interviews

  • “Since the array is sorted, we can halve the search space at every step, which gives us O(log n).”
  • “In terms of space, the recursion depth is O(n), so for large inputs I’d convert it to a loop.”
  • “This has overlapping subproblems, so memoization takes it from exponential to linear.”
  • “I’d watch out for integer overflow here; the result doesn’t fit in a long, so I’d use BigInteger or take it modulo.”
  • “The base case handles the empty range, and each call strictly shrinks the input, so it always terminates.”
  • “I’d cap the recursion depth or rewrite it with an explicit stack on the heap.”
  • “Binary search works on any monotonic predicate, not just on sorted arrays.”
  • “The naive version recomputes the same subproblems, which is why it’s exponential.”

Notes based on the Fundamentals of Backend course (Ronin Engineer), rewritten in my own words.