Data Structures & AlgorithmsRecursion

Common Recursive Patterns

LevelIntermediate

Duration60 mins

TopicRecursion

3 / 4

Binary Recursion (Two Calls)

The Power of Splitting in Two

We've seen recursion with one call (factorial) and recursion with two calls sharing subproblems (Fibonacci). Now we explore binary recursion more broadly—any recursive pattern where a function makes exactly two recursive calls.

Binary recursion is ubiquitous in computer science because so many fundamental structures and algorithms naturally split into two parts:

Binary trees have left and right subtrees
Divide-and-conquer algorithms split problems in half
Decision trees branch on yes/no conditions
Range-based operations recursively process first and second halves

Understanding binary recursion deeply prepares you for tree traversals, sorting algorithms, and the elegant world of divide-and-conquer.

What You Will Learn

By the end of this page, you will understand the general structure of binary recursive functions, how to analyze their time and space complexity, the critical distinction between overlapping and non-overlapping binary recursion, and classic examples that demonstrate this powerful pattern.

Anatomy of Binary Recursion

A binary recursive function has this general structure:

function solve(problem):
    if problem is simple (base case):
        return direct solution
    
    left_result = solve(left sub-problem)     // First recursive call
    right_result = solve(right sub-problem)   // Second recursive call
    
    return combine(left_result, right_result)

The key characteristics are:

Two recursive calls — not one, not three or more, exactly two
Sub-problems — each call receives a smaller/simpler version of the original
Combination step — results from both calls are merged into the final answer

The precise nature of the sub-problems determines the algorithm's efficiency.

Two Fundamentally Different Cases

Case 1: Non-overlapping subproblems (Divide and Conquer)

The two recursive calls work on completely separate parts of the problem:

Binary search on left half OR right half (only one call executes)
Merge sort on first half AND second half (disjoint partitions)
Binary tree: left subtree and right subtree (distinct node sets)

No computation is repeated. Total work is often O(n) or O(n log n).

Case 2: Overlapping subproblems (Dynamic Programming territory)

The two recursive calls share sub-sub-problems:

Fibonacci: fib(n-1) and fib(n-2) both need fib(n-3)

Naive recursion is exponential; memoization or DP is required.

Recognizing which case you're in is crucial for choosing the right approach.

The Split Question

Ask yourself: "Do the two recursive calls operate on completely independent data, or do they share sub-computations?"

• Independent → Divide and conquer, clean O(n log n) or better • Overlapping → Need memoization/DP to avoid exponential blowup

Example: Computing Array Sum with Binary Recursion

Let's examine a simple problem solved with binary recursion: computing the sum of an array. While this can be done iteratively or with linear recursion, the binary recursive approach illustrates divide-and-conquer thinking.

binary-sum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Compute array sum using binary recursion (divide and conquer).
 * 
 * Strategy: Split array in half, sum each half, add results.
 * 
 * Time Complexity: O(n) - each element visited exactly once
 * Space Complexity: O(log n) - recursion depth
 */
function binarySum(arr: number[], left: number, right: number): number {
    // Base case: single element range
    if (left === right) {
        return arr[left];
    }
    
    // Base case: empty range (shouldn't happen with valid input)
    if (left > right) {
        return 0;
    }
    
    // Find midpoint to split the range
    const mid = Math.floor((left + right) / 2);
    
    // Recursive calls on DISJOINT halves
    const leftSum = binarySum(arr, left, mid);       // First half
    const rightSum = binarySum(arr, mid + 1, right); // Second half
    
    // Combine results
    return leftSum + rightSum;
}
 
// Helper to simplify the interface
function sumArray(arr: number[]): number {
    if (arr.length === 0) return 0;
    return binarySum(arr, 0, arr.length - 1);
}
 
// Example usage
const numbers = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(sumArray(numbers)); // 36
 
// Trace for [1, 2, 3, 4]:
//   binarySum([1,2,3,4], 0, 3)
//     binarySum([1,2,3,4], 0, 1)    - left half
//       binarySum([1,2,3,4], 0, 0) → 1
//       binarySum([1,2,3,4], 1, 1) → 2
//       → 1 + 2 = 3
//     binarySum([1,2,3,4], 2, 3)    - right half
//       binarySum([1,2,3,4], 2, 2) → 3
//       binarySum([1,2,3,4], 3, 3) → 4
//       → 3 + 4 = 7
//     → 3 + 7 = 10

Why O(n) Time?

Even though we make two recursive calls at each level, each element is processed exactly once. The recursion tree has:

n leaf nodes (base cases, each element)
n-1 internal nodes (combination steps)
Total: 2n-1 = O(n) nodes

Why O(log n) Space?

The recursion depth equals the number of times we can halve the array:

Array of 8 elements → depth of 3 (8 → 4 → 2 → 1)
Array of n elements → depth of log₂(n)

This is a key advantage over linear recursion's O(n) space!

When Is This Approach Useful?

For simple array summation, iteration or linear recursion is simpler. Binary recursion shines when:

• The operation is expensive and parallelizable (sum both halves simultaneously) • The problem requires divide-and-conquer structure (merge sort, quick sort) • Working with naturally binary structures (binary trees)

This example is a stepping stone to understanding more complex divide-and-conquer algorithms.

Example: Finding Maximum with Binary Recursion

Another classic example demonstrates how binary recursion finds the maximum (or minimum) element in an array.

binary-max.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Find maximum element using binary recursion.
 * 
 * Strategy: Split in half, find max of each half, return greater.
 * 
 * Time: O(n) - each element checked once
 * Space: O(log n) - recursion depth
 */
function binaryMax(arr: number[], left: number, right: number): number {
    // Base case: single element
    if (left === right) {
        return arr[left];
    }
    
    // Two elements - compare directly (optimization)
    if (right - left === 1) {
        return Math.max(arr[left], arr[right]);
    }
    
    // Split and conquer
    const mid = Math.floor((left + right) / 2);
    const leftMax = binaryMax(arr, left, mid);
    const rightMax = binaryMax(arr, mid + 1, right);
    
    // Combine: maximum of the two maxes
    return Math.max(leftMax, rightMax);
}
 
/**
 * Simultaneous min/max - single pass returning both!
 * 
 * This demonstrates how binary recursion can be more efficient
 * than two separate passes when finding multiple values.
 */
function binaryMinMax(
    arr: number[], 
    left: number, 
    right: number
): [number, number] {
    // Base case: single element is both min and max
    if (left === right) {
        return [arr[left], arr[left]];
    }
    
    // Two elements: one comparison gives both
    if (right - left === 1) {
        return arr[left] < arr[right] 
            ? [arr[left], arr[right]] 
            : [arr[right], arr[left]];
    }
    
    // Split and conquer
    const mid = Math.floor((left + right) / 2);
    const [leftMin, leftMax] = binaryMinMax(arr, left, mid);
    const [rightMin, rightMax] = binaryMinMax(arr, mid + 1, right);
    
    // Combine: min of mins, max of maxes
    return [Math.min(leftMin, rightMin), Math.max(leftMax, rightMax)];
}
 
// Usage
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(binaryMax(arr, 0, arr.length - 1)); // 9
console.log(binaryMinMax(arr, 0, arr.length - 1)); // [1, 9]

The Min-Max Efficiency Insight

Finding both minimum and maximum with binary recursion uses fewer comparisons than two linear scans:

Two linear scans: 2(n-1) = 2n - 2 comparisons

Binary min-max: Roughly 3n/2 - 2 comparisons

This is a 25% reduction! The improvement comes from:

Base case of 2 elements: 1 comparison gives both min and max
Each combine step: 2 comparisons (min of mins, max of maxes)

This is a practical demonstration of how divide-and-conquer can outperform obvious approaches.

Binary Recursion and Tree Processing

Binary recursion is the natural language for processing binary trees. Every binary tree operation—traversal, search, modification—maps directly to recurring on left and right subtrees.

tree-operations.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Binary tree node definition
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Count total nodes in binary tree.
 * Classic binary recursion: count left + count right + 1
 */
function countNodes(root: TreeNode | null): number {
    // Base case: empty tree
    if (root === null) return 0;
    
    // Recursive case: this node (1) + all nodes in subtrees
    return 1 + countNodes(root.left) + countNodes(root.right);
}
 
/**
 * Compute height (max depth) of binary tree.
 * Height = max of left height and right height, plus 1
 */
function treeHeight(root: TreeNode | null): number {
    // Base case: empty tree has height -1 (or 0 depending on convention)
    if (root === null) return -1;
    
    // Recursive case: 1 + max height of subtrees
    const leftHeight = treeHeight(root.left);
    const rightHeight = treeHeight(root.right);
    return 1 + Math.max(leftHeight, rightHeight);
}
 
/**
 * Sum all values in the tree.
 */
function treeSum(root: TreeNode | null): number {
    if (root === null) return 0;
    return root.value + treeSum(root.left) + treeSum(root.right);
}
 
/**
 * Check if tree contains a value.
 * Uses short-circuit evaluation for efficiency.
 */
function contains(root: TreeNode | null, target: number): boolean {
    if (root === null) return false;
    if (root.value === target) return true;
    
    // Check left subtree, only check right if left fails
    return contains(root.left, target) || contains(root.right, target);
}
 
/**
 * Check if two trees are structurally identical with same values.
 * Both subtrees must match for trees to be equal.
 */
function treesEqual(a: TreeNode | null, b: TreeNode | null): boolean {
    // Both null - equal
    if (a === null && b === null) return true;
    
    // One null, other not - not equal
    if (a === null || b === null) return false;
    
    // Both exist - check value and both subtrees
    return a.value === b.value && 
           treesEqual(a.left, b.left) && 
           treesEqual(a.right, b.right);
}
 
/**
 * Mirror (invert) a binary tree.
 * Swap left and right subtrees recursively.
 */
function mirrorTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return null;
    
    // Recursively mirror both subtrees, then swap
    const mirroredLeft = mirrorTree(root.left);
    const mirroredRight = mirrorTree(root.right);
    
    root.left = mirroredRight;
    root.right = mirroredLeft;
    
    return root;
}

The Universal Pattern

Notice how every tree function follows the same pattern:

Base case: Handle the empty tree (null/None)
Process current node: Do something with the current node's value
Recurse on both subtrees: Call function on left and right children
Combine results: Merge the recursive results into the final answer

This pattern is so fundamental that once you internalize it, binary tree problems become almost formulaic.

Tree Traversals Are Binary Recursion

Inorder, preorder, and postorder traversals are all binary recursion:

• Preorder: process, recurse left, recurse right • Inorder: recurse left, process, recurse right • Postorder: recurse left, recurse right, process

The only difference is when you process the current node relative to the recursive calls.

Complexity Analysis of Binary Recursion

Binary recursion creates a tree of recursive calls. Understanding this tree's shape determines the algorithm's complexity.

The Recurrence Relation

For binary recursion splitting problem size by half:

T(n) = 2T(n/2) + f(n)

Where:

2 = number of recursive calls
n/2 = size of each subproblem
f(n) = work done at current level (combination step)

This is the Master Theorem form, which gives us:

If f(n) = O(1): T(n) = O(n)

Example: Binary tree node counting (O(1) per node, n nodes total)

If f(n) = O(n): T(n) = O(n log n)

Example: Merge sort (O(n) merge step at each level, log n levels)

If f(n) = O(n²): T(n) = O(n²)

Example: Certain algorithms with quadratic combination steps

Converting Mermaid diagram...

Binary Recursion Complexity Patterns
Problem Pattern	Subproblem Size	Work per Level	Total Time
Tree traversal	n/2, n/2	O(1) per node	O(n)
Array processing (divide)	n/2, n/2	O(1) combine	O(n)
Merge sort	n/2, n/2	O(n) merge	O(n log n)
Fibonacci (naive)	n-1, n-2	O(1)	O(2ⁿ) - overlap!
Maximum subarray	n/2, n/2	O(n) cross	O(n log n)

Space Complexity

For non-overlapping binary recursion:

Space = O(recursion depth)

Splitting in half: O(log n) depth
Tree traversal: O(tree height), which is O(log n) for balanced, O(n) for skewed

This logarithmic space is a key advantage of divide-and-conquer over linear approaches.

The Master Theorem (Simplified)

For recurrence T(n) = aT(n/b) + f(n):

• If work grows slower than branching: T(n) = Θ(n^(log_b a)) • If work grows same as branching: T(n) = Θ(n^(log_b a) log n) • If work grows faster than branching: T(n) = Θ(f(n))

For binary recursion halving inputs (a=2, b=2), the critical value is n^(log_2 2) = n¹ = n.

Powerful Example: Fast Exponentiation

Binary recursion enables one of the most elegant optimizations in computing: reducing exponentiation from O(n) to O(log n) multiplications.

The insight: instead of multiplying x by itself n times, we can halve the exponent at each step:

x^n = (x^(n/2))² when n is even x^n = x · x^(n-1) when n is odd

fast-power.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Fast exponentiation using binary recursion.
 * 
 * Key insight:
 *   x^n = (x^(n/2))^2     if n is even
 *   x^n = x * x^(n-1)     if n is odd
 * 
 * Time: O(log n) - exponent halves each step
 * Space: O(log n) - recursion depth
 */
function fastPower(x: number, n: number): number {
    // Base cases
    if (n === 0) return 1;
    if (n === 1) return x;
    
    // n is even: x^n = (x^(n/2))^2
    if (n % 2 === 0) {
        const half = fastPower(x, n / 2);
        return half * half;  // Only ONE recursive call, then square
    }
    
    // n is odd: x^n = x * x^(n-1)
    return x * fastPower(x, n - 1);
}
 
console.log(fastPower(2, 10));   // 1024
console.log(fastPower(2, 20));   // 1048576
console.log(fastPower(2, 100));  // 1.2676506002282294e+30
 
// Trace for fastPower(2, 10):
// fastPower(2, 10)               n=10 (even)
//   fastPower(2, 5)              n=5 (odd)
//     fastPower(2, 4)            n=4 (even)
//       fastPower(2, 2)          n=2 (even)
//         fastPower(2, 1) = 2    n=1 (base case)
//       = 2 * 2 = 4
//     = 4 * 4 = 16
//   = 2 * 16 = 32
// = 32 * 32 = 1024
// 
// Only 5 multiplication operations for 2^10!
// Linear would need 9 multiplications.
 
 
/**
 * Iterative version using binary representation.
 * Even more efficient - no recursion overhead.
 */
function fastPowerIterative(x: number, n: number): number {
    let result = 1;
    let base = x;
    
    while (n > 0) {
        // If current bit is 1, multiply result by current base
        if (n % 2 === 1) {
            result *= base;
        }
        // Square the base and move to next bit
        base *= base;
        n = Math.floor(n / 2);
    }
    
    return result;
}

Why Is This Binary Recursion?

At first glance, this looks like single recursion—there's only one recursive call per invocation. But conceptually, it's the binary representation of the exponent that drives the algorithm:

10 in binary = 1010 = 2³ + 2¹

2^10 = 2^8 × 2^2 = 256 × 4 = 1024

Each bit of n represents whether to include a squared power. The "binary" in binary recursion here refers to the halving structure of the problem, not the number of recursive calls.

Applications

Fast exponentiation is used in:

Cryptography: RSA encryption requires computing (message)^e mod n for extremely large exponents
Matrix exponentiation: Computing Fibonacci in O(log n) time
Competitive programming: Any problem involving large powers with modular arithmetic

The Power of Halving

Whenever you can halve a problem at each step, you get O(log n) complexity. This is the secret behind binary search, fast exponentiation, and many divide-and-conquer algorithms. Look for opportunities to halve!

Binary Search: Selective Binary Recursion

Binary search is an interesting case: it has the structure of binary recursion (splitting in half) but only makes one recursive call per invocation. Instead of processing both halves, it chooses which half to continue with.

binary-search.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Recursive binary search.
 * 
 * Unlike true binary recursion, this makes only ONE
 * recursive call - we choose which half to search.
 * 
 * Time: O(log n) - halving search space each step
 * Space: O(log n) - recursion depth
 */
function binarySearch(
    arr: number[], 
    target: number, 
    left: number, 
    right: number
): number {
    // Base case: not found
    if (left > right) {
        return -1;
    }
    
    const mid = Math.floor((left + right) / 2);
    
    // Found!
    if (arr[mid] === target) {
        return mid;
    }
    
    // Choose which half to search (NOT BOTH)
    if (target < arr[mid]) {
        return binarySearch(arr, target, left, mid - 1);    // Left half only
    } else {
        return binarySearch(arr, target, mid + 1, right);   // Right half only
    }
}
 
// Usage
const sorted = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(sorted, 7, 0, sorted.length - 1));   // 3
console.log(binarySearch(sorted, 8, 0, sorted.length - 1));   // -1
console.log(binarySearch(sorted, 19, 0, sorted.length - 1));  // 9
 
// Trace for searching 7 in [1,3,5,7,9,11,13,15,17,19]:
// binarySearch(arr, 7, 0, 9)
//   mid = 4, arr[4] = 9, 7 < 9, go left
// binarySearch(arr, 7, 0, 3)
//   mid = 1, arr[1] = 3, 7 > 3, go right
// binarySearch(arr, 7, 2, 3)
//   mid = 2, arr[2] = 5, 7 > 5, go right
// binarySearch(arr, 7, 3, 3)
//   mid = 3, arr[3] = 7, FOUND!
//   return 3

Linear vs Binary Recursion in Search

Linear recursion: Process one element, recurse on rest

Time: O(n) per search
Example: Searching unsorted array

Selective binary recursion: Choose one half, ignore other

Time: O(log n) per search
Example: Binary search on sorted array

Full binary recursion: Process both halves

Time: O(n) total (visit all elements)
Example: Finding max in unsorted array

Binary search is O(log n) precisely because it eliminates half the possibilities at each step rather than processing everything.

The Taxonomy of Recursion

• Linear recursion: One call, processes linearly • Binary recursion: Two calls, may process both OR choose one • Multiple recursion: More than two calls (tree exploration, permutations)

Understanding where your algorithm falls helps predict its complexity.

Summary: The Binary Recursion Pattern

Binary recursion—functions that make two recursive calls—is one of the most powerful and prevalent patterns in computer science. From data structures to algorithms, understanding this pattern unlocks an enormous range of problems.

Key Takeaways

•Binary recursion makes two recursive calls — The critical question is whether they operate on overlapping or disjoint subproblems
•Non-overlapping (divide and conquer) leads to efficient O(n) or O(n log n) algorithms without memoization needed
•Overlapping subproblems (like Fibonacci) create exponential blowup unless addressed with memoization or DP
•Binary trees are natural binary recursion — Every tree operation recurs on left and right subtrees
•Splitting in half gives O(log n) depth — This is why divide-and-conquer often achieves O(n log n) time with O(log n) space
•Fast exponentiation demonstrates the power of halving: O(n) → O(log n)
•Binary search is selective binary recursion — Choosing one half rather than processing both

What's Next

With binary recursion mastered, we're ready to explore the powerful paradigm that systematically applies it: divide and conquer. This strategy explicitly structures problems as splitting, conquering recursively, and combining—leading to elegant solutions for sorting, searching, computational geometry, and beyond.

Page Complete

You now understand binary recursion deeply—its structure, its complexity implications, and its manifestation in trees, arrays, and mathematical operations. This foundation is essential for divide-and-conquer algorithms and tree-based problem solving.

3 / 4

Loading learning content...

Data Structures & AlgorithmsRecursion

Common Recursive Patterns

LevelIntermediate

Duration60 mins

TopicRecursion

3 / 4

Binary Recursion (Two Calls)

The Power of Splitting in Two

Binary recursion is ubiquitous in computer science because so many fundamental structures and algorithms naturally split into two parts:

Binary trees have left and right subtrees
Divide-and-conquer algorithms split problems in half
Decision trees branch on yes/no conditions
Range-based operations recursively process first and second halves

Understanding binary recursion deeply prepares you for tree traversals, sorting algorithms, and the elegant world of divide-and-conquer.

What You Will Learn

Anatomy of Binary Recursion

A binary recursive function has this general structure:

function solve(problem):
    if problem is simple (base case):
        return direct solution
    
    left_result = solve(left sub-problem)     // First recursive call
    right_result = solve(right sub-problem)   // Second recursive call
    
    return combine(left_result, right_result)

The key characteristics are:

Two recursive calls — not one, not three or more, exactly two
Sub-problems — each call receives a smaller/simpler version of the original
Combination step — results from both calls are merged into the final answer

The precise nature of the sub-problems determines the algorithm's efficiency.

Two Fundamentally Different Cases

Case 1: Non-overlapping subproblems (Divide and Conquer)

The two recursive calls work on completely separate parts of the problem:

Binary search on left half OR right half (only one call executes)
Merge sort on first half AND second half (disjoint partitions)
Binary tree: left subtree and right subtree (distinct node sets)

No computation is repeated. Total work is often O(n) or O(n log n).

Case 2: Overlapping subproblems (Dynamic Programming territory)

The two recursive calls share sub-sub-problems:

Fibonacci: fib(n-1) and fib(n-2) both need fib(n-3)

Naive recursion is exponential; memoization or DP is required.

Recognizing which case you're in is crucial for choosing the right approach.

The Split Question

Ask yourself: "Do the two recursive calls operate on completely independent data, or do they share sub-computations?"

• Independent → Divide and conquer, clean O(n log n) or better • Overlapping → Need memoization/DP to avoid exponential blowup

Example: Computing Array Sum with Binary Recursion

binary-sum.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Compute array sum using binary recursion (divide and conquer).
 * 
 * Strategy: Split array in half, sum each half, add results.
 * 
 * Time Complexity: O(n) - each element visited exactly once
 * Space Complexity: O(log n) - recursion depth
 */
function binarySum(arr: number[], left: number, right: number): number {
    // Base case: single element range
    if (left === right) {
        return arr[left];
    }
    
    // Base case: empty range (shouldn't happen with valid input)
    if (left > right) {
        return 0;
    }
    
    // Find midpoint to split the range
    const mid = Math.floor((left + right) / 2);
    
    // Recursive calls on DISJOINT halves
    const leftSum = binarySum(arr, left, mid);       // First half
    const rightSum = binarySum(arr, mid + 1, right); // Second half
    
    // Combine results
    return leftSum + rightSum;
}
 
// Helper to simplify the interface
function sumArray(arr: number[]): number {
    if (arr.length === 0) return 0;
    return binarySum(arr, 0, arr.length - 1);
}
 
// Example usage
const numbers = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(sumArray(numbers)); // 36
 
// Trace for [1, 2, 3, 4]:
//   binarySum([1,2,3,4], 0, 3)
//     binarySum([1,2,3,4], 0, 1)    - left half
//       binarySum([1,2,3,4], 0, 0) → 1
//       binarySum([1,2,3,4], 1, 1) → 2
//       → 1 + 2 = 3
//     binarySum([1,2,3,4], 2, 3)    - right half
//       binarySum([1,2,3,4], 2, 2) → 3
//       binarySum([1,2,3,4], 3, 3) → 4
//       → 3 + 4 = 7
//     → 3 + 7 = 10

Why O(n) Time?

Even though we make two recursive calls at each level, each element is processed exactly once. The recursion tree has:

n leaf nodes (base cases, each element)
n-1 internal nodes (combination steps)
Total: 2n-1 = O(n) nodes

Why O(log n) Space?

The recursion depth equals the number of times we can halve the array:

Array of 8 elements → depth of 3 (8 → 4 → 2 → 1)
Array of n elements → depth of log₂(n)

This is a key advantage over linear recursion's O(n) space!

When Is This Approach Useful?

For simple array summation, iteration or linear recursion is simpler. Binary recursion shines when:

This example is a stepping stone to understanding more complex divide-and-conquer algorithms.

Example: Finding Maximum with Binary Recursion

Another classic example demonstrates how binary recursion finds the maximum (or minimum) element in an array.

binary-max.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Find maximum element using binary recursion.
 * 
 * Strategy: Split in half, find max of each half, return greater.
 * 
 * Time: O(n) - each element checked once
 * Space: O(log n) - recursion depth
 */
function binaryMax(arr: number[], left: number, right: number): number {
    // Base case: single element
    if (left === right) {
        return arr[left];
    }
    
    // Two elements - compare directly (optimization)
    if (right - left === 1) {
        return Math.max(arr[left], arr[right]);
    }
    
    // Split and conquer
    const mid = Math.floor((left + right) / 2);
    const leftMax = binaryMax(arr, left, mid);
    const rightMax = binaryMax(arr, mid + 1, right);
    
    // Combine: maximum of the two maxes
    return Math.max(leftMax, rightMax);
}
 
/**
 * Simultaneous min/max - single pass returning both!
 * 
 * This demonstrates how binary recursion can be more efficient
 * than two separate passes when finding multiple values.
 */
function binaryMinMax(
    arr: number[], 
    left: number, 
    right: number
): [number, number] {
    // Base case: single element is both min and max
    if (left === right) {
        return [arr[left], arr[left]];
    }
    
    // Two elements: one comparison gives both
    if (right - left === 1) {
        return arr[left] < arr[right] 
            ? [arr[left], arr[right]] 
            : [arr[right], arr[left]];
    }
    
    // Split and conquer
    const mid = Math.floor((left + right) / 2);
    const [leftMin, leftMax] = binaryMinMax(arr, left, mid);
    const [rightMin, rightMax] = binaryMinMax(arr, mid + 1, right);
    
    // Combine: min of mins, max of maxes
    return [Math.min(leftMin, rightMin), Math.max(leftMax, rightMax)];
}
 
// Usage
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(binaryMax(arr, 0, arr.length - 1)); // 9
console.log(binaryMinMax(arr, 0, arr.length - 1)); // [1, 9]

The Min-Max Efficiency Insight

Finding both minimum and maximum with binary recursion uses fewer comparisons than two linear scans:

Two linear scans: 2(n-1) = 2n - 2 comparisons

Binary min-max: Roughly 3n/2 - 2 comparisons

This is a 25% reduction! The improvement comes from:

Base case of 2 elements: 1 comparison gives both min and max
Each combine step: 2 comparisons (min of mins, max of maxes)

This is a practical demonstration of how divide-and-conquer can outperform obvious approaches.

Binary Recursion and Tree Processing

Binary recursion is the natural language for processing binary trees. Every binary tree operation—traversal, search, modification—maps directly to recurring on left and right subtrees.

tree-operations.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Binary tree node definition
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Count total nodes in binary tree.
 * Classic binary recursion: count left + count right + 1
 */
function countNodes(root: TreeNode | null): number {
    // Base case: empty tree
    if (root === null) return 0;
    
    // Recursive case: this node (1) + all nodes in subtrees
    return 1 + countNodes(root.left) + countNodes(root.right);
}
 
/**
 * Compute height (max depth) of binary tree.
 * Height = max of left height and right height, plus 1
 */
function treeHeight(root: TreeNode | null): number {
    // Base case: empty tree has height -1 (or 0 depending on convention)
    if (root === null) return -1;
    
    // Recursive case: 1 + max height of subtrees
    const leftHeight = treeHeight(root.left);
    const rightHeight = treeHeight(root.right);
    return 1 + Math.max(leftHeight, rightHeight);
}
 
/**
 * Sum all values in the tree.
 */
function treeSum(root: TreeNode | null): number {
    if (root === null) return 0;
    return root.value + treeSum(root.left) + treeSum(root.right);
}
 
/**
 * Check if tree contains a value.
 * Uses short-circuit evaluation for efficiency.
 */
function contains(root: TreeNode | null, target: number): boolean {
    if (root === null) return false;
    if (root.value === target) return true;
    
    // Check left subtree, only check right if left fails
    return contains(root.left, target) || contains(root.right, target);
}
 
/**
 * Check if two trees are structurally identical with same values.
 * Both subtrees must match for trees to be equal.
 */
function treesEqual(a: TreeNode | null, b: TreeNode | null): boolean {
    // Both null - equal
    if (a === null && b === null) return true;
    
    // One null, other not - not equal
    if (a === null || b === null) return false;
    
    // Both exist - check value and both subtrees
    return a.value === b.value && 
           treesEqual(a.left, b.left) && 
           treesEqual(a.right, b.right);
}
 
/**
 * Mirror (invert) a binary tree.
 * Swap left and right subtrees recursively.
 */
function mirrorTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return null;
    
    // Recursively mirror both subtrees, then swap
    const mirroredLeft = mirrorTree(root.left);
    const mirroredRight = mirrorTree(root.right);
    
    root.left = mirroredRight;
    root.right = mirroredLeft;
    
    return root;
}

The Universal Pattern

Notice how every tree function follows the same pattern:

Base case: Handle the empty tree (null/None)
Process current node: Do something with the current node's value
Recurse on both subtrees: Call function on left and right children
Combine results: Merge the recursive results into the final answer

This pattern is so fundamental that once you internalize it, binary tree problems become almost formulaic.

Tree Traversals Are Binary Recursion

Inorder, preorder, and postorder traversals are all binary recursion:

• Preorder: process, recurse left, recurse right • Inorder: recurse left, process, recurse right • Postorder: recurse left, recurse right, process

The only difference is when you process the current node relative to the recursive calls.

Complexity Analysis of Binary Recursion

Binary recursion creates a tree of recursive calls. Understanding this tree's shape determines the algorithm's complexity.

The Recurrence Relation

For binary recursion splitting problem size by half:

T(n) = 2T(n/2) + f(n)

Where:

2 = number of recursive calls
n/2 = size of each subproblem
f(n) = work done at current level (combination step)

This is the Master Theorem form, which gives us:

If f(n) = O(1): T(n) = O(n)

Example: Binary tree node counting (O(1) per node, n nodes total)

If f(n) = O(n): T(n) = O(n log n)

Example: Merge sort (O(n) merge step at each level, log n levels)

If f(n) = O(n²): T(n) = O(n²)

Example: Certain algorithms with quadratic combination steps

Converting Mermaid diagram...

Binary Recursion Complexity Patterns
Problem Pattern	Subproblem Size	Work per Level	Total Time
Tree traversal	n/2, n/2	O(1) per node	O(n)
Array processing (divide)	n/2, n/2	O(1) combine	O(n)
Merge sort	n/2, n/2	O(n) merge	O(n log n)
Fibonacci (naive)	n-1, n-2	O(1)	O(2ⁿ) - overlap!
Maximum subarray	n/2, n/2	O(n) cross	O(n log n)

Space Complexity

For non-overlapping binary recursion:

Space = O(recursion depth)

Splitting in half: O(log n) depth
Tree traversal: O(tree height), which is O(log n) for balanced, O(n) for skewed

This logarithmic space is a key advantage of divide-and-conquer over linear approaches.

The Master Theorem (Simplified)

For recurrence T(n) = aT(n/b) + f(n):

• If work grows slower than branching: T(n) = Θ(n^(log_b a)) • If work grows same as branching: T(n) = Θ(n^(log_b a) log n) • If work grows faster than branching: T(n) = Θ(f(n))

For binary recursion halving inputs (a=2, b=2), the critical value is n^(log_2 2) = n¹ = n.

Powerful Example: Fast Exponentiation

Binary recursion enables one of the most elegant optimizations in computing: reducing exponentiation from O(n) to O(log n) multiplications.

The insight: instead of multiplying x by itself n times, we can halve the exponent at each step:

x^n = (x^(n/2))² when n is even x^n = x · x^(n-1) when n is odd

fast-power.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Fast exponentiation using binary recursion.
 * 
 * Key insight:
 *   x^n = (x^(n/2))^2     if n is even
 *   x^n = x * x^(n-1)     if n is odd
 * 
 * Time: O(log n) - exponent halves each step
 * Space: O(log n) - recursion depth
 */
function fastPower(x: number, n: number): number {
    // Base cases
    if (n === 0) return 1;
    if (n === 1) return x;
    
    // n is even: x^n = (x^(n/2))^2
    if (n % 2 === 0) {
        const half = fastPower(x, n / 2);
        return half * half;  // Only ONE recursive call, then square
    }
    
    // n is odd: x^n = x * x^(n-1)
    return x * fastPower(x, n - 1);
}
 
console.log(fastPower(2, 10));   // 1024
console.log(fastPower(2, 20));   // 1048576
console.log(fastPower(2, 100));  // 1.2676506002282294e+30
 
// Trace for fastPower(2, 10):
// fastPower(2, 10)               n=10 (even)
//   fastPower(2, 5)              n=5 (odd)
//     fastPower(2, 4)            n=4 (even)
//       fastPower(2, 2)          n=2 (even)
//         fastPower(2, 1) = 2    n=1 (base case)
//       = 2 * 2 = 4
//     = 4 * 4 = 16
//   = 2 * 16 = 32
// = 32 * 32 = 1024
// 
// Only 5 multiplication operations for 2^10!
// Linear would need 9 multiplications.
 
 
/**
 * Iterative version using binary representation.
 * Even more efficient - no recursion overhead.
 */
function fastPowerIterative(x: number, n: number): number {
    let result = 1;
    let base = x;
    
    while (n > 0) {
        // If current bit is 1, multiply result by current base
        if (n % 2 === 1) {
            result *= base;
        }
        // Square the base and move to next bit
        base *= base;
        n = Math.floor(n / 2);
    }
    
    return result;
}

Why Is This Binary Recursion?

At first glance, this looks like single recursion—there's only one recursive call per invocation. But conceptually, it's the binary representation of the exponent that drives the algorithm:

10 in binary = 1010 = 2³ + 2¹

2^10 = 2^8 × 2^2 = 256 × 4 = 1024

Each bit of n represents whether to include a squared power. The "binary" in binary recursion here refers to the halving structure of the problem, not the number of recursive calls.

Applications

Fast exponentiation is used in:

Cryptography: RSA encryption requires computing (message)^e mod n for extremely large exponents
Matrix exponentiation: Computing Fibonacci in O(log n) time
Competitive programming: Any problem involving large powers with modular arithmetic

The Power of Halving

Binary Search: Selective Binary Recursion

binary-search.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Recursive binary search.
 * 
 * Unlike true binary recursion, this makes only ONE
 * recursive call - we choose which half to search.
 * 
 * Time: O(log n) - halving search space each step
 * Space: O(log n) - recursion depth
 */
function binarySearch(
    arr: number[], 
    target: number, 
    left: number, 
    right: number
): number {
    // Base case: not found
    if (left > right) {
        return -1;
    }
    
    const mid = Math.floor((left + right) / 2);
    
    // Found!
    if (arr[mid] === target) {
        return mid;
    }
    
    // Choose which half to search (NOT BOTH)
    if (target < arr[mid]) {
        return binarySearch(arr, target, left, mid - 1);    // Left half only
    } else {
        return binarySearch(arr, target, mid + 1, right);   // Right half only
    }
}
 
// Usage
const sorted = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(sorted, 7, 0, sorted.length - 1));   // 3
console.log(binarySearch(sorted, 8, 0, sorted.length - 1));   // -1
console.log(binarySearch(sorted, 19, 0, sorted.length - 1));  // 9
 
// Trace for searching 7 in [1,3,5,7,9,11,13,15,17,19]:
// binarySearch(arr, 7, 0, 9)
//   mid = 4, arr[4] = 9, 7 < 9, go left
// binarySearch(arr, 7, 0, 3)
//   mid = 1, arr[1] = 3, 7 > 3, go right
// binarySearch(arr, 7, 2, 3)
//   mid = 2, arr[2] = 5, 7 > 5, go right
// binarySearch(arr, 7, 3, 3)
//   mid = 3, arr[3] = 7, FOUND!
//   return 3

Linear vs Binary Recursion in Search

Linear recursion: Process one element, recurse on rest

Time: O(n) per search
Example: Searching unsorted array

Selective binary recursion: Choose one half, ignore other

Time: O(log n) per search
Example: Binary search on sorted array

Full binary recursion: Process both halves

Time: O(n) total (visit all elements)
Example: Finding max in unsorted array

Binary search is O(log n) precisely because it eliminates half the possibilities at each step rather than processing everything.

The Taxonomy of Recursion

Understanding where your algorithm falls helps predict its complexity.

Summary: The Binary Recursion Pattern

Key Takeaways

•Binary recursion makes two recursive calls — The critical question is whether they operate on overlapping or disjoint subproblems
•Non-overlapping (divide and conquer) leads to efficient O(n) or O(n log n) algorithms without memoization needed
•Overlapping subproblems (like Fibonacci) create exponential blowup unless addressed with memoization or DP
•Binary trees are natural binary recursion — Every tree operation recurs on left and right subtrees
•Splitting in half gives O(log n) depth — This is why divide-and-conquer often achieves O(n log n) time with O(log n) space
•Fast exponentiation demonstrates the power of halving: O(n) → O(log n)
•Binary search is selective binary recursion — Choosing one half rather than processing both

What's Next

Page Complete

3 / 4