Card 06/ 08
Divide and Conquer in Python, Java and TypeScript
The largest value by halves, instrumented to print the calls and work on each level.
The largest value by halves is a function that takes an array and two bounds, returns the item itself when the bounds meet, and otherwise calls itself on each half and keeps the larger answer. The listings below add a counter for each level of the recursion, so that a run prints how many calls and comparisons each level made: the recursion tree's level totals, measured instead of drawn. Each runs on 7 3 9 1 6 8 2 5.
The largest value by halves, with calls and comparisons per level, in each language
from dataclasses import dataclass
@dataclass
class Level:
calls: int = 0
comparisons: int = 0
def largest(items: list[int], low: int, high: int, levels: list[Level], depth: int = 0) -> int:
if depth == len(levels):
levels.append(Level())
levels[depth].calls += 1
if low == high:
return items[low]
mid = (low + high) // 2
left = largest(items, low, mid, levels, depth + 1)
right = largest(items, mid + 1, high, levels, depth + 1)
levels[depth].comparisons += 1
return left if left >= right else right
numbers = [7, 3, 9, 1, 6, 8, 2, 5]
levels: list[Level] = []
answer = largest(numbers, 0, len(numbers) - 1, levels)
print("largest of", " ".join(map(str, numbers)), "is", answer)
for depth, level in enumerate(levels):
print(f"level {depth}: calls {level.calls}, comparisons {level.comparisons}")
calls = sum(level.calls for level in levels)
comparisons = sum(level.comparisons for level in levels)
print(f"total: calls {calls}, comparisons {comparisons}")
print("built-in max:", max(numbers))largest of 7 3 9 1 6 8 2 5 is 9
level 0: calls 1, comparisons 1
level 1: calls 2, comparisons 2
level 2: calls 4, comparisons 4
level 3: calls 8, comparisons 0
total: calls 15, comparisons 7
built-in max: 9import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class DivideAndConquerCode {
static final class Level {
int calls;
int comparisons;
}
static int largest(int[] items, int low, int high, List<Level> levels, int depth) {
if (depth == levels.size()) {
levels.add(new Level());
}
levels.get(depth).calls++;
if (low == high) {
return items[low];
}
int mid = low + (high - low) / 2;
int left = largest(items, low, mid, levels, depth + 1);
int right = largest(items, mid + 1, high, levels, depth + 1);
levels.get(depth).comparisons++;
return left >= right ? left : right;
}
public static void main(String[] args) {
int[] numbers = {7, 3, 9, 1, 6, 8, 2, 5};
List<Level> levels = new ArrayList<>();
int answer = largest(numbers, 0, numbers.length - 1, levels, 0);
System.out.println("largest of 7 3 9 1 6 8 2 5 is " + answer);
int calls = 0;
int comparisons = 0;
for (int depth = 0; depth < levels.size(); depth++) {
Level level = levels.get(depth);
System.out.println("level " + depth + ": calls " + level.calls
+ ", comparisons " + level.comparisons);
calls += level.calls;
comparisons += level.comparisons;
}
System.out.println("total: calls " + calls + ", comparisons " + comparisons);
System.out.println("built-in max: " + Arrays.stream(numbers).max().getAsInt());
}
}largest of 7 3 9 1 6 8 2 5 is 9
level 0: calls 1, comparisons 1
level 1: calls 2, comparisons 2
level 2: calls 4, comparisons 4
level 3: calls 8, comparisons 0
total: calls 15, comparisons 7
built-in max: 9interface Level {
calls: number;
comparisons: number;
}
function largest(items: number[], low: number, high: number, levels: Level[], depth = 0): number {
if (depth === levels.length) {
levels.push({ calls: 0, comparisons: 0 });
}
levels[depth].calls++;
if (low === high) {
return items[low];
}
const mid = Math.floor((low + high) / 2);
const left = largest(items, low, mid, levels, depth + 1);
const right = largest(items, mid + 1, high, levels, depth + 1);
levels[depth].comparisons++;
return left >= right ? left : right;
}
const numbers = [7, 3, 9, 1, 6, 8, 2, 5];
const levels: Level[] = [];
const answer = largest(numbers, 0, numbers.length - 1, levels);
console.log(`largest of ${numbers.join(" ")} is ${answer}`);
levels.forEach((level, depth) => {
console.log(`level ${depth}: calls ${level.calls}, comparisons ${level.comparisons}`);
});
const calls = levels.reduce((sum, level) => sum + level.calls, 0);
const comparisons = levels.reduce((sum, level) => sum + level.comparisons, 0);
console.log(`total: calls ${calls}, comparisons ${comparisons}`);
console.log(`built-in max: ${Math.max(...numbers)}`);largest of 7 3 9 1 6 8 2 5 is 9
level 0: calls 1, comparisons 1
level 1: calls 2, comparisons 2
level 2: calls 4, comparisons 4
level 3: calls 8, comparisons 0
total: calls 15, comparisons 7
built-in max: 9All three printed the same seven lines. The highlighted lines are the three steps: the midpoint is the divide, the two calls are the conquer, and the final comparison is the combine. Java computes the midpoint as low + (high - low) / 2 so that the sum of two large indices cannot overflow an int, as in Binary Search; Python's integers do not overflow, and TypeScript's numbers stay exact well beyond any array index.
The counts are the recursion tree of T(n) = 2T(n/2) + O(1). The calls double on each level, 1, 2, 4 and 8, for 15 in all, which is 2n − 1. The comparisons double too until the leaves, which make none, for 7 in all, which is n − 1. Work that grows on the way down means the leaves win, case 1 of the master theorem, and the cost is O(n).
The bounds matter more than they look. Passing low and high lets every call read the one shared array. Slicing the halves instead, items[:mid] in Python or Arrays.copyOfRange in Java, copies n items on every level, which makes the work outside the calls O(n), the recurrence 2T(n/2) + O(n), and the cost O(n log n) for a job a loop does in O(n). The recursion goes only log₂ n + 1 levels deep, 21 for a million items, so the call stack is never at risk here.
Each language also has the largest value built in, and each is a single loop of n − 1 comparisons. Python's max(numbers) printed 9, and raises ValueError on an empty list. Java's Arrays.stream(numbers).max() returns an OptionalInt, empty for an empty array, which is why the listing calls getAsInt(). TypeScript's Math.max(...numbers) spreads the array into separate arguments, and in a run under Node 24 it returned 1 for an array of 10,000 ones but threw a RangeError for an array of a million; for large arrays, a loop or numbers.reduce has no such limit. In real code, use the built-in or a loop. The halving version is here for the shape it gives the recurrence.
← → move through sections and cards