Anatomy of Recursion - Learning Module

Loading content...

0/276

The Recursive Case — How to Reduce

The Engine of Recursion

If the base case is the anchor that stops recursion, the recursive case is the engine that propels it forward. The recursive case embodies the central insight of recursive problem-solving: every complex problem can be expressed as a simpler version of itself, plus some additional work.

In this page, we dissect the recursive case with surgical precision. We'll explore how to reduce problems effectively, how to combine sub-solutions correctly, and how these two operations work together to create elegant recursive solutions.

Learning Objectives

By completing this page, you will:

• Understand the dual role of the recursive case: reduction and combination • Master different reduction strategies for various problem types • Learn to design combination logic that constructs correct solutions • Recognize the invariants that must hold between reduction and combination • Develop intuition for choosing optimal reduction strategies

The Two Operations of the Recursive Case

Every recursive case performs two fundamental operations:

Operation 1: Reduction

Transform the current problem into one or more smaller subproblems of the same type. The smaller problems must be:

Genuinely smaller (closer to a base case)
The same kind of problem (solvable by the same function)
Together, sufficient to solve the original problem

Operation 2: Combination

Take the solution(s) to the subproblem(s) and construct the solution to the original problem. This might involve:

Arithmetic operations (add, multiply, max, min)
Logical operations (and, or)
Data structure operations (concatenate, merge, prepend)
Selection (choose one result, filter results)

reduction_combination.ts
TypeScript
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
// Anatomy of the recursive case:
 
function factorial(n: number): number {
    if (n === 0) return 1;  // Base case
    
    // RECURSIVE CASE:
    
    // OPERATION 1: REDUCTION
    // Transform n → (n - 1)
    // This makes the problem smaller: computing (n-1)! instead of n!
    const smaller = n - 1;
    
    // Make the recursive call on the reduced problem
    const subSolution = factorial(smaller);
    
    // OPERATION 2: COMBINATION
    // Use the sub-solution to build the answer to the original problem
    // We know: n! = n × (n-1)!
    const solution = n * subSolution;
    
    return solution;
}
 
// More compactly written (same logic, condensed):
function factorialCompact(n: number): number {
    if (n === 0) return 1;
    return n * factorialCompact(n - 1);  // Reduction and combination in one line
    //     ^                   ^^^^^^^
    //     |                   Reduction: n → (n-1)
    //     Combination: multiply by n
}

The Reduction-Combination Duality

Reduction and combination are dual operations. The reduction breaks the problem apart; the combination puts the solution back together. They must be designed together to ensure correctness. If you change how you reduce, you typically must change how you combine.

Reduction Strategies: Ways to Make Problems Smaller

There are several common strategies for reducing problems. The choice of strategy depends on the problem structure and affects both efficiency and code clarity.

Strategy 1: Subtract One (Linear Reduction)

Reduce the problem size by exactly one unit. This creates a linear chain of subproblems.

n → n-1 (factorial, countdown)
arr → arr.slice(1) (sum, reverse)
str → str.slice(1) (string processing)

subtract_one.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Linear reduction: decrease by 1 each call
// Results in O(n) recursive calls
 
function sumArray(arr: number[]): number {
    if (arr.length === 0) return 0;
    
    // REDUCTION: Remove one element (first)
    // arr → arr.slice(1)
    // [1,2,3] → [2,3] → [3] → []
    
    return arr[0] + sumArray(arr.slice(1));
    //                       ^^^^^^^^^^^^^ 
    //                       Array is smaller by 1
}
 
function countDown(n: number): void {
    if (n < 0) return;
    console.log(n);
    
    // REDUCTION: Decrease by 1
    countDown(n - 1);
    //        ^^^^^
    //        n is smaller by 1
}

Strategy 2: Divide in Half (Logarithmic Reduction)

Cut the problem in half (or some constant fraction). This creates a logarithmic depth of recursive calls—dramatically more efficient for large inputs.

n → n/2 (binary search, exponentiation by squaring)
arr → arr.slice(0, mid) (merge sort, binary search)

divide_half.ts
TypeScript
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
// Logarithmic reduction: divide by 2 each call
// Results in O(log n) recursive calls
 
function binarySearch(arr: number[], target: number, 
                      lo: number = 0, hi: number = arr.length - 1): number {
    if (lo > hi) return -1;
    
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    
    // REDUCTION: Search space halves each time
    // [lo...hi] → [lo...mid-1] or [mid+1...hi]
    // Each subproblem is half the size!
    
    if (arr[mid] > target) {
        return binarySearch(arr, target, lo, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, hi);
    }
}
 
function fastPower(x: number, n: number): number {
    if (n === 0) return 1;
    
    // REDUCTION: Halve the exponent when even
    if (n % 2 === 0) {
        const half = fastPower(x, n / 2);  // n → n/2
        return half * half;
    }
    
    return x * fastPower(x, n - 1);  // Fall back to subtract-one for odd
}

Strategy 3: Split into Two (Binary Recursion)

Create two subproblems that together cover the original problem. Both branches are explored (unlike binary search where only one branch is taken).

Fibonacci: n → (n-1, n-2)
Tree traversal: node → (left, right)
Merge sort: arr → (firstHalf, secondHalf)

split_two.ts
TypeScript
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
// Binary recursion: two recursive calls per invocation
// Total calls can be O(2^n) or O(n) depending on structure
 
function fibonacci(n: number): number {
    if (n <= 1) return n;
    
    // REDUCTION: Create TWO subproblems
    // Both are solved, results are combined
    return fibonacci(n - 1) + fibonacci(n - 2);
    //              ^^^^^^^   ^^^^^^^^^^^^^^^
    //              Subproblem 1   Subproblem 2
}
 
// Tree height - binary reduction matching tree structure
interface TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
function treeHeight(node: TreeNode | null): number {
    if (node === null) return 0;
    
    // REDUCTION: Solve for left and right subtrees
    const leftHeight = treeHeight(node.left);
    const rightHeight = treeHeight(node.right);
    
    // COMBINATION: Take max of children, add 1 for current node
    return 1 + Math.max(leftHeight, rightHeight);
}

Strategy 4: Enumerate Choices (Multiple Recursion)

When the problem has multiple options at each step, recurse on each option. Common in combinatorial problems.

Subsets: for each element, include it or don't
Permutations: for each position, try each remaining element
N-Queens: for each row, try each valid column

enumerate_choices.ts
TypeScript
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
// Multiple recursion: branch for each choice
// Often leads to O(2^n) or O(n!) complexity
 
function subsets(nums: number[]): number[][] {
    if (nums.length === 0) return [[]];
    
    const first = nums[0];
    const rest = nums.slice(1);
    
    // REDUCTION: Solve for array without first element
    const subsetsWithoutFirst = subsets(rest);
    
    // ENUMERATION: For the first element, we have a choice:
    // - Don't include it: use subsetsWithoutFirst as-is
    // - Include it: add first to each subset in subsetsWithoutFirst
    
    const subsetsWithFirst = subsetsWithoutFirst.map(s => [first, ...s]);
    
    // COMBINATION: Merge all possibilities
    return [...subsetsWithoutFirst, ...subsetsWithFirst];
}
 
// Example: subsets([1, 2])
// subsets([2]) returns [[], [2]]
// subsetsWithFirst adds 1: [[1], [1,2]]
// Result: [[], [2], [1], [1,2]]

Summary of Reduction Strategies
Strategy	Reduction Pattern	Typical Depth	When to Use
Subtract One	n → n-1, arr → arr[1:]	O(n)	Simple linear processing
Divide in Half	n → n/2, arr → first/second half	O(log n)	Search, divide-and-conquer
Split into Two	Problem → Two subproblems	O(n) or O(log n)	Trees, merge sort
Enumerate Choices	Problem → Multiple branches	O(2^n) or worse	Combinatorial problems

Combination Strategies: Building Solutions from Parts

Once you have solutions to subproblems, you must combine them into the solution for the original problem. The combination strategy depends on what kind of answer you're computing.

Combination Type 1: Aggregation

Combine sub-results using an aggregation operation:

Sum: a + b (total, count)
Product: a * b (factorial, combinations)
Max/Min: Math.max(a, b) (optimization)
And/Or: a && b, a || b (boolean queries)

aggregation.ts
TypeScript
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
// Aggregation: Combine multiple sub-results into one value
 
// Sum aggregation
function sumRange(lo: number, hi: number): number {
    if (lo > hi) return 0;
    return lo + sumRange(lo + 1, hi);
    //     ^   ^^^^^^^^^^^^^^^^^^^^^^
    //     Current value + Sum of rest
}
 
// Max aggregation
function maxArray(arr: number[]): number {
    if (arr.length === 1) return arr[0];
    const restMax = maxArray(arr.slice(1));
    return Math.max(arr[0], restMax);
    //     ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    //     Max of current vs. max of rest
}
 
// Boolean aggregation (exists/all)
function anyPositive(arr: number[]): boolean {
    if (arr.length === 0) return false;
    return arr[0] > 0 || anyPositive(arr.slice(1));
    //     ^^^^^^^^^^    ^^^^^^^^^^^^^^^^^^^^^^
    //     Current check OR check of rest (short-circuits!)
}

Combination Type 2: Construction

Build a new data structure by assembling parts:

String: char + recursiveResult or recursiveResult + char
Array: [element, ...recursiveResult]
Object: merge(partial, recursive)

construction.ts
TypeScript
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
// Construction: Build data structures piece by piece
 
// String construction
function reverseString(str: string): string {
    if (str.length <= 1) return str;
    return reverseString(str.slice(1)) + str[0];
    //     ^^^^^^^^^^^^^^^^^^^^^^^^^^   ^^^^^^
    //     Reversed rest              + First char at end
}
 
// Array construction
function doubleAll(arr: number[]): number[] {
    if (arr.length === 0) return [];
    return [arr[0] * 2, ...doubleAll(arr.slice(1))];
    //     ^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^^^
    //     Doubled first   Concatenate with doubled rest
}
 
// Filtered construction
function filterPositive(arr: number[]): number[] {
    if (arr.length === 0) return [];
    const rest = filterPositive(arr.slice(1));
    
    // Conditionally include current element
    if (arr[0] > 0) {
        return [arr[0], ...rest];  // Include
    } else {
        return rest;               // Exclude
    }
}

Combination Type 3: Selection

Choose between sub-solutions or pick the best one:

Best of options: choose the better path
First valid: stop at first success
All valid: collect all that work

selection.ts
TypeScript
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
// Selection: Choose among sub-solutions
 
// Best-of selection (optimization)
function minCoins(coins: number[], amount: number): number {
    if (amount === 0) return 0;
    if (amount < 0) return Infinity;
    
    let minCount = Infinity;
    
    for (const coin of coins) {
        // Reduce: try using each coin
        const subResult = minCoins(coins, amount - coin);
        
        // Select: take the minimum across all choices
        minCount = Math.min(minCount, 1 + subResult);
    }
    
    return minCount;
}
 
// First-valid selection (search)
function findPath(maze: number[][], x: number, y: number): boolean {
    // Base cases
    if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length) return false;
    if (maze[x][y] === 1) return false;  // Wall
    if (x === maze.length - 1 && y === maze[0].length - 1) return true;  // Goal
    
    maze[x][y] = 1;  // Mark visited
    
    // Selection: return true if ANY direction works
    return findPath(maze, x + 1, y) ||
           findPath(maze, x - 1, y) ||
           findPath(maze, x, y + 1) ||
           findPath(maze, x, y - 1);
    // Short-circuits on first success!
}

Combination Type 4: Merge

Combine two structured solutions into one (divide and conquer pattern):

Merge sorted halves (merge sort)
Combine tree results

merge.ts
TypeScript
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
// Merge: Combine two structured sub-solutions
 
function mergeSort(arr: number[]): number[] {
    // Base case
    if (arr.length <= 1) return arr;
    
    // REDUCTION: Split into two halves
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    
    // COMBINATION: Merge two sorted arrays
    return merge(left, right);
}
 
function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
    
    // Interleave elements in sorted order
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    // Append remaining elements
    return [...result, ...left.slice(i), ...right.slice(j)];
}

The Reduction-Combination Contract

Reduction and combination are not independent—they form a contract. The way you reduce the problem determines what information you have available for combination, and vice versa.

The Contract States:

If I reduce the problem this way, I commit to having all the necessary information to combine the sub-solution(s) with the remaining part to produce the correct answer.

Breaking this contract leads to incorrect solutions, often in subtle ways.

TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// ❌ BROKEN CONTRACT
 
function brokenProduct(arr: number[]): number {
    if (arr.length === 0) return 0;
    // Contract violation: reducing by removing
    // first, but ADDING instead of multiplying
    
    // Reduction: remove first element
    const rest = brokenProduct(arr.slice(1));
    
    // Combination: WRONG operation!
    return arr[0] + rest;  // Should be *
}
 
// brokenProduct([2, 3, 4])
// = 2 + brokenProduct([3, 4])
// = 2 + (3 + brokenProduct([4]))
// = 2 + (3 + (4 + brokenProduct([])))
// = 2 + 3 + 4 + 0 = 9
// Should be 2 * 3 * 4 = 24!

TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// ✅ CORRECT CONTRACT
 
function product(arr: number[]): number {
    if (arr.length === 0) return 1;
    // Correct: identity for multiplication is 1
    
    // Reduction: remove first element
    const rest = product(arr.slice(1));
    
    // Combination: Multiplication matches
    // the product we're computing
    return arr[0] * rest;
}
 
// product([2, 3, 4])
// = 2 * product([3, 4])
// = 2 * (3 * product([4]))
// = 2 * (3 * (4 * product([])))
// = 2 * 3 * 4 * 1 = 24 ✓

Matching Reduction and Combination

The combination operation must correctly "undo" the reduction. If you reduce by removing an element, you combine by processing that element. If you split in half, you must merge the halves. The mathematical relationship between the original problem and subproblems must be reflected in your combination logic.

Verifying the Contract:

To check if your reduction and combination form a valid contract, ask:

Does reduction lose information? Whatever you "set aside" during reduction must be available for combination.
Does combination use all the available information? The sub-solution plus any set-aside information should fully determine the answer.
Is the relationship mathematically correct? For example: sum(arr) = arr[0] + sum(arr[1:]) only if addition is our combination operation.

Work Before vs. After the Recursive Call

A crucial design decision is when to do work relative to the recursive call. This affects both correctness and the possibility of tail-call optimization.

Work Before (Pre-order Processing)

Process the current element/node before recursing. Results are computed during the descent phase.

Work After (Post-order Processing)

Recurse first, then process using the sub-result. Results are computed during the ascent phase.

Work Around (In-order Processing)

Do some work, recurse on one part, do more work, recurse on another part. Common in tree traversals.

work_timing.ts
TypeScript
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
// Demonstrating work timing with tree traversal
 
interface Node {
    value: number;
    left: Node | null;
    right: Node | null;
}
 
// PRE-ORDER: Work BEFORE recursive calls
function preorder(node: Node | null, result: number[] = []): number[] {
    if (node === null) return result;
    
    result.push(node.value);     // ← Work (process current)
    preorder(node.left, result);  // Recurse left
    preorder(node.right, result); // Recurse right
    
    return result;
}
// Order: Current → Left → Right
 
// POST-ORDER: Work AFTER recursive calls
function postorder(node: Node | null, result: number[] = []): number[] {
    if (node === null) return result;
    
    postorder(node.left, result);  // Recurse left
    postorder(node.right, result); // Recurse right
    result.push(node.value);       // ← Work (process current)
    
    return result;
}
// Order: Left → Right → Current
 
// IN-ORDER: Work BETWEEN recursive calls
function inorder(node: Node | null, result: number[] = []): number[] {
    if (node === null) return result;
    
    inorder(node.left, result);   // Recurse left
    result.push(node.value);      // ← Work (process current)
    inorder(node.right, result);  // Recurse right
    
    return result;
}
// Order: Left → Current → Right

Why Does Timing Matter?

Result dependencies: If the result depends on sub-results, work must happen after the recursive call.
Side effects ordering: If you're printing or modifying state, the order matters.
Tail recursion: If the recursive call is the last operation, tail-call optimization may apply.

When the current answer depends on sub-results, work MUST happen after the recursive call.

TypeScript
1
2
3
4
5
6
7
8
9
// Factorial: We need (n-1)! before we can compute n!
function factorial(n: number): number {
    if (n === 0) return 1;
    
    const subResult = factorial(n - 1);  // Must complete first!
    return n * subResult;                 // Work happens AFTER
    //          ^^^^^^^^^ 
    //          We need this value to do the multiplication
}

Tail Recursion and Optimization

When the recursive call is the very last operation (tail position), some languages can optimize the call to use constant stack space. This is called Tail Call Optimization (TCO). The accumulator pattern often enables tail recursion. We'll explore this in depth in a later module.

Recursive Case Examples Across Problem Types

Let's examine several well-designed recursive cases to solidify the pattern recognition.

Problem: Find the greatest common divisor of two numbers.

Key insight: gcd(a, b) = gcd(b, a mod b)

TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function gcd(a: number, b: number): number {
    // BASE CASE: GCD(a, 0) = a
    if (b === 0) return a;
    
    // RECURSIVE CASE:
    // Reduction: (a, b) → (b, a mod b)
    // This is logarithmic! Each step reduces the problem size significantly.
    // gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6
    
    return gcd(b, a % b);
    //     ^^^^^^^^^^^^^^^
    // Combination: None! The sub-result IS the answer.
    // This is called "pure tail recursion" - just return the result.
}
 
// Note: No combination step because the mathematical relationship
// is direct: gcd(a,b) equals gcd(b, a mod b), period.

A Framework for Designing Recursive Cases

Let's consolidate everything into a systematic framework for designing recursive cases.

Recursive Case Design Framework

•Identify the problem's natural decomposition — How does this problem naturally break into smaller pieces? Array → first + rest? Tree → root + children? Number → smaller number?
•Choose a reduction strategy — Will you subtract one, divide in half, split into parts, or enumerate choices? The choice affects complexity and structure.
•Determine what information to preserve — What must you keep from the current level to combine with the sub-result? The current element? The pivot? A running count?
•Design the combination logic — Given the sub-solution(s) and the preserved information, how do you build the answer? Add? Multiply? Concatenate? Select?
•Verify the reduction-combination contract — Does the sub-solution plus preserved info fully determine the answer? Is the combination mathematically correct?
•Consider work timing — Should work happen before or after the recursive call? Does it matter for correctness? Can you enable tail recursion?

framework_example.ts
TypeScript
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
// Example: Design a function to compute array product
 
/*
STEP 1: Natural decomposition
  Array → first element + rest of array
 
STEP 2: Reduction strategy
  Subtract one: arr → arr.slice(1)
  Linear complexity O(n)
 
STEP 3: Preserved information
  The first element arr[0]
 
STEP 4: Combination logic
  product(arr) = arr[0] * product(arr.slice(1))
  Operation: multiplication
 
STEP 5: Verify contract
  If product(rest) is correct, then arr[0] * product(rest) = product(arr) ✓
  Base case: empty array returns 1 (identity for multiplication) ✓
 
STEP 6: Work timing
  Multiplication happens AFTER recursion returns (post-order)
  Result depends on sub-result, so this is necessary
*/
 
function arrayProduct(arr: number[]): number {
    // Base case
    if (arr.length === 0) return 1;  // Multiplicative identity
    
    // Recursive case
    return arr[0] * arrayProduct(arr.slice(1));
    //     ^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^
    //     Preserved   Reduction
    //     info        (smaller array)
    //
    // Combination: multiplication
}

Summary: Mastering the Recursive Case

The recursive case is where the real work of recursion happens—where problems are decomposed and solutions are constructed. Let's consolidate the key insights:

Key Takeaways

•The recursive case has two operations: Reduction (making the problem smaller) and combination (building the answer from sub-solutions).
•Reduction strategies include subtract-one (linear), divide-in-half (logarithmic), split-into-two (binary), and enumerate-choices (exponential).
•Combination strategies include aggregation, construction, selection, and merge.
•The reduction-combination contract must be consistent—how you break apart must match how you put together.
•Work timing matters: Post-order when results depend on sub-results; pre-order enables potential tail-call optimization.
•Use the design framework to systematically construct recursive cases for any problem.

What's Next:

With both base cases and recursive cases mastered, we're ready to explore one of the most powerful mental tools in recursion: the leap of faith. This is the mindset that allows you to trust your recursive calls and focus on the current level of the problem, dramatically simplifying recursive thinking.

Page Complete

You now understand the mechanics of the recursive case—how to reduce problems and combine solutions. You can analyze different reduction strategies, design appropriate combination logic, and verify the consistency of your approach. Next, we'll unlock the 'leap of faith' that makes recursive thinking intuitive rather than exhausting.