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:
- A base case: the smallest case with an immediate answer and no further calls. This is the stopping condition.
- 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
- Define the function
f: what it takes and what it returns. - Identify the base case.
- Find the recurrence: split the problem into subproblems closer to the base case.
- 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, returnF(n)(F(0) = 0,F(1) = 1). The solution is in section 3.2. - “Pascal’s Triangle”: generate the first
numRowsrows 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.
2.1. Linear search
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;
}
2.2. Binary search
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)andCollections.binarySearch(list, key)return the index when found, and-(insertionPoint) - 1otherwise, 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.binarySearchon aLinkedListstill works, but reachingmidmeans 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.
- Linear search: https://liveexample.pearsoncmg.com/dsanimation13ejava/LinearSearcheBook.html
- Binary search: https://liveexample.pearsoncmg.com/dsanimation13ejava/BinarySearcheBook.html
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 fornfrom 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 negativen, return1.0 / pow(x, -n)withdouble, and watch out forn = Integer.MIN_VALUE, because-nis still negative. - (d) has the closed form
n(n+1)/2, O(1). Recursing withn = 100,000can cause aStackOverflowError. 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 = 1000it 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), overflowinglongvery early, so you needBigInteger. If the problem asks for the result modulo10⁹ + 7, uselongand 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) - 1return value. - Explain why naive Fibonacci is exponential and how memoization brings it to O(n).
- Remember the overflow limits:
intoverflows from13!andF(47),longonly holds up to20!andF(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.
What do you need before you can use binary search?
Sorted data (more generally, a monotonic condition) and O(1) random access.
On a linked list binary search loses its advantage, because just reaching the middle costs O(n).
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.