Data Structures & AlgorithmsRecursive Problem-Solving Strategies

Recursive Problem-Solving Strategies

LevelIntermediate

Duration75 mins

TopicRecursive Problem-Solving Strategies

4 / 4

Practice Problems and Patterns

From Theory to Mastery

You've learned to identify recursive structure, decompose problems, and combine solutions. Now it's time to cement these skills through deliberate practice.

This page presents a curated collection of problems organized by pattern. For each problem, we'll analyze the recursive structure, design the solution, and implement it. The goal isn't just to solve these specific problems—it's to internalize the patterns so deeply that you recognize them instantly in new contexts.

After working through this material, you'll have a robust mental library of recursive problem patterns that you can draw from throughout your career.

How to Use This Page

For maximum learning: (1) Read the problem statement, (2) Try to identify the pattern before reading the analysis, (3) Attempt the solution yourself, (4) Compare with the provided solution, (5) Note any differences in approach.

Pattern Library Overview

Before diving into problems, let's organize the major recursive patterns you should recognize:

The Eight Core Recursive Patterns

Linear Recursion — Process one element, recurse on rest
Binary Recursion — Split in two, recurse on both halves
Tree Recursion — Follow the tree's natural structure
Backtracking — Try choices, undo if they fail
Divide-and-Conquer — Split, solve independently, merge
Accumulator Pattern — Carry state through recursive calls
Mutual Recursion — Multiple functions call each other
Generate-and-Test — Generate candidates, filter valid ones

Each pattern has signature characteristics and typical problem types.

Pattern Recognition Quick Reference
Pattern	Key Signal	Typical Problems
Linear	Process elements sequentially	List operations, string processing
Binary	Natural halving	Search, balanced trees, merge sort
Tree	Hierarchical data	All tree operations
Backtracking	Try-and-undo	Puzzles, constraint satisfaction
Divide-Conquer	Independent subproblems	Sorting, optimization
Accumulator	Need running state	Path tracking, tail recursion
Mutual	Alternating rules	Parsers, state machines
Generate-Test	Enumerate then filter	Combinatorics

Tree Pattern Problems

Trees are the quintessential recursive structure. Every tree problem follows the pattern:

solve(node) = combine(node.value, solve(node.left), solve(node.right))

Problem 1: Check if Two Trees are Identical

Problem: Given two binary trees, determine if they are structurally identical with the same values.

Pattern Recognition:

Structure: Binary tree comparison
Decomposition: Compare roots, then compare left and right subtrees
Combination: AND (both subtrees must match)
Base case: Both null (identical), one null (not identical)

identical_trees
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
interface TreeNode {
    value: number;
    left?: TreeNode;
    right?: TreeNode;
}
 
function areIdentical(t1: TreeNode | undefined, t2: TreeNode | undefined): boolean {
    // Base case 1: both empty
    if (!t1 && !t2) return true;
    
    // Base case 2: one empty, one not
    if (!t1 || !t2) return false;
    
    // Recursive case: check current + both subtrees
    return (
        t1.value === t2.value &&
        areIdentical(t1.left, t2.left) &&
        areIdentical(t1.right, t2.right)
    );
}
 
// Test
const tree1: TreeNode = { value: 1, left: { value: 2 }, right: { value: 3 } };
const tree2: TreeNode = { value: 1, left: { value: 2 }, right: { value: 3 } };
const tree3: TreeNode = { value: 1, left: { value: 2 }, right: { value: 4 } };
 
console.log(areIdentical(tree1, tree2));  // true
console.log(areIdentical(tree1, tree3));  // false

Problem 2: Invert a Binary Tree

Problem: Mirror a binary tree by swapping left and right children at every node.

Pattern Recognition:

Structure: Binary tree transformation
Decomposition: Invert subtrees, then swap them
Combination: Construction (build new node with swapped children)
Base case: Empty tree inverts to empty

invert_tree
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
interface TreeNode {
    value: number;
    left?: TreeNode;
    right?: TreeNode;
}
 
function invertTree(node: TreeNode | undefined): TreeNode | undefined {
    // Base case: empty tree
    if (!node) return undefined;
    
    // Recurse on children, then swap
    const invertedLeft = invertTree(node.left);
    const invertedRight = invertTree(node.right);
    
    // Construct inverted node (children swapped)
    return {
        value: node.value,
        left: invertedRight,   // Right becomes left
        right: invertedLeft,   // Left becomes right
    };
}
 
// In-place version (modifies original tree)
function invertTreeInPlace(node: TreeNode | undefined): TreeNode | undefined {
    if (!node) return undefined;
    
    // Swap children
    [node.left, node.right] = [node.right, node.left];
    
    // Recurse
    invertTreeInPlace(node.left);
    invertTreeInPlace(node.right);
    
    return node;
}

Backtracking Pattern Problems

Backtracking explores possibilities by making choices, recursing, and undoing choices if they lead to dead ends.

Problem 3: Generate All Permutations

Problem: Given a list of distinct integers, return all possible permutations.

Pattern Recognition:

Structure: Choice at each position (which element to place)
Decomposition: Fix one element, permute the rest
Combination: Collect all valid orderings
Base case: All positions filled (one permutation complete)

permutations
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
function permutations(nums: number[]): number[][] {
    const results: number[][] = [];
    
    function backtrack(current: number[], remaining: number[]) {
        // Base case: all elements placed
        if (remaining.length === 0) {
            results.push([...current]);
            return;
        }
        
        // Try each remaining element in next position
        for (let i = 0; i < remaining.length; i++) {
            // Choose
            current.push(remaining[i]);
            const newRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
            
            // Explore
            backtrack(current, newRemaining);
            
            // Unchoose (backtrack)
            current.pop();
        }
    }
    
    backtrack([], nums);
    return results;
}
 
console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Problem 4: N-Queens

Problem: Place N queens on an N×N chessboard so no two queens attack each other.

Pattern Recognition:

Structure: Place queens row by row, each row has N choices
Decomposition: Place queen in current row, solve for remaining rows
Combination: Collect all valid complete placements
Constraints: No two queens share row, column, or diagonal
Base case: All N queens placed successfully

n_queens
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
function solveNQueens(n: number): string[][] {
    const results: string[][] = [];
    const board: string[][] = Array.from({ length: n }, () => 
        Array(n).fill('.')
    );
    
    function isValid(row: number, col: number): boolean {
        // Check column
        for (let r = 0; r < row; r++) {
            if (board[r][col] === 'Q') return false;
        }
        
        // Check upper-left diagonal
        for (let r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
            if (board[r][c] === 'Q') return false;
        }
        
        // Check upper-right diagonal
        for (let r = row - 1, c = col + 1; r >= 0 && c < n; r--, c++) {
            if (board[r][c] === 'Q') return false;
        }
        
        return true;
    }
    
    function backtrack(row: number) {
        // Base case: all queens placed
        if (row === n) {
            results.push(board.map(r => r.join('')));
            return;
        }
        
        // Try each column in current row
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';      // Choose
                backtrack(row + 1);          // Explore
                board[row][col] = '.';       // Unchoose
            }
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log(solveNQueens(4));
// [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]

Divide-and-Conquer Problems

Divide-and-conquer splits problems into independent subproblems, solves them, and merges results.

Problem 5: Count Inversions

Problem: Count pairs (i, j) where i < j but array[i] > array[j]. This measures how 'unsorted' an array is.

Pattern Recognition:

Insight: Modified merge sort can count inversions during merge
Decomposition: Count inversions in left half, right half, and across halves
Combination: Sum all three counts
Cross-half inversions counted during merge (sorted elements from left > elements from right)

count_inversions
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
function countInversions(arr: number[]): number {
    // Returns [sortedArray, inversionCount]
    function mergeSort(nums: number[]): [number[], number] {
        if (nums.length <= 1) return [nums, 0];
        
        const mid = Math.floor(nums.length / 2);
        const [leftSorted, leftInv] = mergeSort(nums.slice(0, mid));
        const [rightSorted, rightInv] = mergeSort(nums.slice(mid));
        const [merged, splitInv] = mergeAndCount(leftSorted, rightSorted);
        
        return [merged, leftInv + rightInv + splitInv];
    }
    
    function mergeAndCount(left: number[], right: number[]): [number[], number] {
        const result: number[] = [];
        let inversions = 0;
        let i = 0, j = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result.push(left[i++]);
            } else {
                result.push(right[j++]);
                // All remaining elements in left are > right[j]
                inversions += left.length - i;
            }
        }
        
        while (i < left.length) result.push(left[i++]);
        while (j < right.length) result.push(right[j++]);
        
        return [result, inversions];
    }
    
    return mergeSort(arr)[1];
}
 
console.log(countInversions([2, 4, 1, 3, 5]));  // 3: (2,1), (4,1), (4,3)
console.log(countInversions([5, 4, 3, 2, 1]));  // 10: fully reversed

Recursion to Dynamic Programming

Many recursive solutions have overlapping subproblems—the same subproblem is solved multiple times. This is where recursion meets dynamic programming.

Problem 6: Fibonacci with Memoization

Problem: Compute the nth Fibonacci number efficiently.

Pattern Recognition:

Naive recursion: Exponential time due to repeated computation
Observation: F(5) requires F(4) and F(3); F(4) also requires F(3)
Solution: Cache results to avoid recomputation

fib_memoization
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
// Naive recursive - O(2^n) - exponential!
function fibNaive(n: number): number {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}
 
// With memoization - O(n) - each subproblem solved once
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 1) return n;
    
    if (memo.has(n)) return memo.get(n)!;
    
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, result);
    return result;
}
 
// Bottom-up DP - O(n) time, O(1) space
function fibDP(n: number): number {
    if (n <= 1) return n;
    
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
 
console.log(fibMemo(40));  // 102334155 - instant
console.log(fibDP(40));    // 102334155 - instant
// fibNaive(40) would take several seconds!

The Recursion-DP Bridge

Memoization transforms exponential recursive solutions into polynomial ones by caching results. This is often the easiest path to a DP solution: start with pure recursion, identify overlapping subproblems, add a cache. The recursive structure guides your thinking; memoization handles efficiency.

Pattern Recognition Exercises

For each problem below, identify the recursive pattern before looking at the solution approach.

Exercise 1: Flatten Nested List

Given a nested list of integers, return a flat list of all integers.

Pattern: Tree recursion (nested structure = tree) Decomposition: For each element, if it's a number, include it; if it's a list, flatten it recursively.

Exercise 2: Letter Combinations of Phone Number

Given a string of digits 2-9, return all letter combinations the digits could represent.

Pattern: Backtracking/Generate-and-test Decomposition: For each digit, try each possible letter, recurse on remaining digits.

Exercise 3: Maximum Subarray (Divide-and-Conquer approach)

Find the contiguous subarray with the largest sum.

Pattern: Divide-and-conquer Decomposition: Max subarray is in left half, right half, or crosses the middle. Find all three, return max.

Exercise 4: Decode Ways

Given a string of digits, count ways to decode it as letters (1='A', 26='Z').

Pattern: Linear recursion with overlapping subproblems (DP) Decomposition: Take 1 digit + decode rest, OR take 2 digits (if valid) + decode rest.

Exercise Classification Summary
Problem	Primary Pattern	Key Insight
Flatten nested list	Tree recursion	Nested structure = implicit tree
Phone number letters	Backtracking	Multiple choices per position
Max subarray (D&C)	Divide-conquer	Cross-boundary case is key
Decode ways	DP/Memoization	Overlapping subproblems

Summary and Mastery Path

Key Takeaways

•Eight core patterns — Linear, binary, tree, backtracking, divide-conquer, accumulator, mutual, generate-test.
•Tree problems follow natural structure — Recurse on subtrees, combine results at each node.
•Backtracking = Try-Explore-Undo — Choose, recurse, unchoose if path fails.
•Divide-conquer splits into independent parts — Key is the merge step.
•Overlapping subproblems call for memoization — Transform exponential to polynomial.
•Pattern recognition accelerates solutions — Build mental library through deliberate practice.

Module Complete!

Congratulations! You've completed the Recursive Problem-Solving Strategies module. You now have a comprehensive framework for approaching any recursive problem: identify structure, choose decomposition strategy, design combination logic, and recognize patterns. Continue practicing with diverse problems to cement these skills into lasting intuition.

4 / 4

Loading learning content...

Data Structures & AlgorithmsRecursive Problem-Solving Strategies

Recursive Problem-Solving Strategies

LevelIntermediate

Duration75 mins

TopicRecursive Problem-Solving Strategies

4 / 4

Practice Problems and Patterns

From Theory to Mastery

You've learned to identify recursive structure, decompose problems, and combine solutions. Now it's time to cement these skills through deliberate practice.

After working through this material, you'll have a robust mental library of recursive problem patterns that you can draw from throughout your career.

How to Use This Page

Pattern Library Overview

Before diving into problems, let's organize the major recursive patterns you should recognize:

The Eight Core Recursive Patterns

Linear Recursion — Process one element, recurse on rest
Binary Recursion — Split in two, recurse on both halves
Tree Recursion — Follow the tree's natural structure
Backtracking — Try choices, undo if they fail
Divide-and-Conquer — Split, solve independently, merge
Accumulator Pattern — Carry state through recursive calls
Mutual Recursion — Multiple functions call each other
Generate-and-Test — Generate candidates, filter valid ones

Each pattern has signature characteristics and typical problem types.

Pattern Recognition Quick Reference
Pattern	Key Signal	Typical Problems
Linear	Process elements sequentially	List operations, string processing
Binary	Natural halving	Search, balanced trees, merge sort
Tree	Hierarchical data	All tree operations
Backtracking	Try-and-undo	Puzzles, constraint satisfaction
Divide-Conquer	Independent subproblems	Sorting, optimization
Accumulator	Need running state	Path tracking, tail recursion
Mutual	Alternating rules	Parsers, state machines
Generate-Test	Enumerate then filter	Combinatorics

Tree Pattern Problems

Trees are the quintessential recursive structure. Every tree problem follows the pattern:

solve(node) = combine(node.value, solve(node.left), solve(node.right))

Problem 1: Check if Two Trees are Identical

Problem: Given two binary trees, determine if they are structurally identical with the same values.

Pattern Recognition:

Structure: Binary tree comparison
Decomposition: Compare roots, then compare left and right subtrees
Combination: AND (both subtrees must match)
Base case: Both null (identical), one null (not identical)

identical_trees
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
interface TreeNode {
    value: number;
    left?: TreeNode;
    right?: TreeNode;
}
 
function areIdentical(t1: TreeNode | undefined, t2: TreeNode | undefined): boolean {
    // Base case 1: both empty
    if (!t1 && !t2) return true;
    
    // Base case 2: one empty, one not
    if (!t1 || !t2) return false;
    
    // Recursive case: check current + both subtrees
    return (
        t1.value === t2.value &&
        areIdentical(t1.left, t2.left) &&
        areIdentical(t1.right, t2.right)
    );
}
 
// Test
const tree1: TreeNode = { value: 1, left: { value: 2 }, right: { value: 3 } };
const tree2: TreeNode = { value: 1, left: { value: 2 }, right: { value: 3 } };
const tree3: TreeNode = { value: 1, left: { value: 2 }, right: { value: 4 } };
 
console.log(areIdentical(tree1, tree2));  // true
console.log(areIdentical(tree1, tree3));  // false

Problem 2: Invert a Binary Tree

Problem: Mirror a binary tree by swapping left and right children at every node.

Pattern Recognition:

Structure: Binary tree transformation
Decomposition: Invert subtrees, then swap them
Combination: Construction (build new node with swapped children)
Base case: Empty tree inverts to empty

invert_tree
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
interface TreeNode {
    value: number;
    left?: TreeNode;
    right?: TreeNode;
}
 
function invertTree(node: TreeNode | undefined): TreeNode | undefined {
    // Base case: empty tree
    if (!node) return undefined;
    
    // Recurse on children, then swap
    const invertedLeft = invertTree(node.left);
    const invertedRight = invertTree(node.right);
    
    // Construct inverted node (children swapped)
    return {
        value: node.value,
        left: invertedRight,   // Right becomes left
        right: invertedLeft,   // Left becomes right
    };
}
 
// In-place version (modifies original tree)
function invertTreeInPlace(node: TreeNode | undefined): TreeNode | undefined {
    if (!node) return undefined;
    
    // Swap children
    [node.left, node.right] = [node.right, node.left];
    
    // Recurse
    invertTreeInPlace(node.left);
    invertTreeInPlace(node.right);
    
    return node;
}

Backtracking Pattern Problems

Backtracking explores possibilities by making choices, recursing, and undoing choices if they lead to dead ends.

Problem 3: Generate All Permutations

Problem: Given a list of distinct integers, return all possible permutations.

Pattern Recognition:

Structure: Choice at each position (which element to place)
Decomposition: Fix one element, permute the rest
Combination: Collect all valid orderings
Base case: All positions filled (one permutation complete)

permutations
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
function permutations(nums: number[]): number[][] {
    const results: number[][] = [];
    
    function backtrack(current: number[], remaining: number[]) {
        // Base case: all elements placed
        if (remaining.length === 0) {
            results.push([...current]);
            return;
        }
        
        // Try each remaining element in next position
        for (let i = 0; i < remaining.length; i++) {
            // Choose
            current.push(remaining[i]);
            const newRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
            
            // Explore
            backtrack(current, newRemaining);
            
            // Unchoose (backtrack)
            current.pop();
        }
    }
    
    backtrack([], nums);
    return results;
}
 
console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Problem 4: N-Queens

Problem: Place N queens on an N×N chessboard so no two queens attack each other.

Pattern Recognition:

Structure: Place queens row by row, each row has N choices
Decomposition: Place queen in current row, solve for remaining rows
Combination: Collect all valid complete placements
Constraints: No two queens share row, column, or diagonal
Base case: All N queens placed successfully

n_queens
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
function solveNQueens(n: number): string[][] {
    const results: string[][] = [];
    const board: string[][] = Array.from({ length: n }, () => 
        Array(n).fill('.')
    );
    
    function isValid(row: number, col: number): boolean {
        // Check column
        for (let r = 0; r < row; r++) {
            if (board[r][col] === 'Q') return false;
        }
        
        // Check upper-left diagonal
        for (let r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
            if (board[r][c] === 'Q') return false;
        }
        
        // Check upper-right diagonal
        for (let r = row - 1, c = col + 1; r >= 0 && c < n; r--, c++) {
            if (board[r][c] === 'Q') return false;
        }
        
        return true;
    }
    
    function backtrack(row: number) {
        // Base case: all queens placed
        if (row === n) {
            results.push(board.map(r => r.join('')));
            return;
        }
        
        // Try each column in current row
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';      // Choose
                backtrack(row + 1);          // Explore
                board[row][col] = '.';       // Unchoose
            }
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log(solveNQueens(4));
// [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]

Divide-and-Conquer Problems

Divide-and-conquer splits problems into independent subproblems, solves them, and merges results.

Problem 5: Count Inversions

Problem: Count pairs (i, j) where i < j but array[i] > array[j]. This measures how 'unsorted' an array is.

Pattern Recognition:

Insight: Modified merge sort can count inversions during merge
Decomposition: Count inversions in left half, right half, and across halves
Combination: Sum all three counts
Cross-half inversions counted during merge (sorted elements from left > elements from right)

count_inversions
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
function countInversions(arr: number[]): number {
    // Returns [sortedArray, inversionCount]
    function mergeSort(nums: number[]): [number[], number] {
        if (nums.length <= 1) return [nums, 0];
        
        const mid = Math.floor(nums.length / 2);
        const [leftSorted, leftInv] = mergeSort(nums.slice(0, mid));
        const [rightSorted, rightInv] = mergeSort(nums.slice(mid));
        const [merged, splitInv] = mergeAndCount(leftSorted, rightSorted);
        
        return [merged, leftInv + rightInv + splitInv];
    }
    
    function mergeAndCount(left: number[], right: number[]): [number[], number] {
        const result: number[] = [];
        let inversions = 0;
        let i = 0, j = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result.push(left[i++]);
            } else {
                result.push(right[j++]);
                // All remaining elements in left are > right[j]
                inversions += left.length - i;
            }
        }
        
        while (i < left.length) result.push(left[i++]);
        while (j < right.length) result.push(right[j++]);
        
        return [result, inversions];
    }
    
    return mergeSort(arr)[1];
}
 
console.log(countInversions([2, 4, 1, 3, 5]));  // 3: (2,1), (4,1), (4,3)
console.log(countInversions([5, 4, 3, 2, 1]));  // 10: fully reversed

Recursion to Dynamic Programming

Many recursive solutions have overlapping subproblems—the same subproblem is solved multiple times. This is where recursion meets dynamic programming.

Problem 6: Fibonacci with Memoization

Problem: Compute the nth Fibonacci number efficiently.

Pattern Recognition:

Naive recursion: Exponential time due to repeated computation
Observation: F(5) requires F(4) and F(3); F(4) also requires F(3)
Solution: Cache results to avoid recomputation

fib_memoization
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
// Naive recursive - O(2^n) - exponential!
function fibNaive(n: number): number {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}
 
// With memoization - O(n) - each subproblem solved once
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 1) return n;
    
    if (memo.has(n)) return memo.get(n)!;
    
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, result);
    return result;
}
 
// Bottom-up DP - O(n) time, O(1) space
function fibDP(n: number): number {
    if (n <= 1) return n;
    
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
 
console.log(fibMemo(40));  // 102334155 - instant
console.log(fibDP(40));    // 102334155 - instant
// fibNaive(40) would take several seconds!

The Recursion-DP Bridge

Pattern Recognition Exercises

For each problem below, identify the recursive pattern before looking at the solution approach.

Exercise 1: Flatten Nested List

Given a nested list of integers, return a flat list of all integers.

Pattern: Tree recursion (nested structure = tree) Decomposition: For each element, if it's a number, include it; if it's a list, flatten it recursively.

Exercise 2: Letter Combinations of Phone Number

Given a string of digits 2-9, return all letter combinations the digits could represent.

Pattern: Backtracking/Generate-and-test Decomposition: For each digit, try each possible letter, recurse on remaining digits.

Exercise 3: Maximum Subarray (Divide-and-Conquer approach)

Find the contiguous subarray with the largest sum.

Pattern: Divide-and-conquer Decomposition: Max subarray is in left half, right half, or crosses the middle. Find all three, return max.

Exercise 4: Decode Ways

Given a string of digits, count ways to decode it as letters (1='A', 26='Z').

Pattern: Linear recursion with overlapping subproblems (DP) Decomposition: Take 1 digit + decode rest, OR take 2 digits (if valid) + decode rest.

Exercise Classification Summary
Problem	Primary Pattern	Key Insight
Flatten nested list	Tree recursion	Nested structure = implicit tree
Phone number letters	Backtracking	Multiple choices per position
Max subarray (D&C)	Divide-conquer	Cross-boundary case is key
Decode ways	DP/Memoization	Overlapping subproblems

Summary and Mastery Path

Key Takeaways

•Eight core patterns — Linear, binary, tree, backtracking, divide-conquer, accumulator, mutual, generate-test.
•Tree problems follow natural structure — Recurse on subtrees, combine results at each node.
•Backtracking = Try-Explore-Undo — Choose, recurse, unchoose if path fails.
•Divide-conquer splits into independent parts — Key is the merge step.
•Overlapping subproblems call for memoization — Transform exponential to polynomial.
•Pattern recognition accelerates solutions — Build mental library through deliberate practice.

Module Complete!

4 / 4