Data Structures & AlgorithmsRecursion

Common Recursive Patterns

LevelIntermediate

Duration60 mins

TopicRecursion

2 / 4

Fibonacci and Overlapping Subproblems

When Recursion Becomes Expensive

Factorial taught us the elegant simplicity of recursion. Now we encounter a pattern that reveals recursion's dangerous side—a function so natural to write yet so catastrophically inefficient that it serves as a cautionary tale in every algorithms course.

The Fibonacci sequence is deceptively simple: each number is the sum of the two preceding numbers. This innocent definition conceals exponential complexity that renders naive recursion practically useless for any meaningful input size. Yet from this failure emerges one of the most important concepts in algorithmic thinking: overlapping subproblems.

Understanding why Fibonacci recursion is slow—and how to fix it—is your gateway to dynamic programming, memoization, and a whole class of optimization techniques that transform exponential algorithms into polynomial ones.

What You Will Learn

By the end of this page, you will understand the Fibonacci sequence and its recursive definition, why naive recursive Fibonacci is exponentially slow, what overlapping subproblems are and how to recognize them, how memoization transforms exponential into linear complexity, and why this pattern is the foundation of dynamic programming.

The Fibonacci Sequence

The Fibonacci sequence is one of the most famous sequences in mathematics, appearing in nature, art, architecture, and computer science. It's defined as:

F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n ≥ 2

The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Each number is the sum of the two before it:

F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8

This simple rule generates a sequence with remarkable mathematical properties.

Fibonacci in Nature and Computing

Fibonacci numbers appear in the spiral arrangement of leaves, the breeding of rabbits (the original motivation for the sequence), the structure of pinecones and sunflowers, and countless other natural phenomena. In computing, they appear in algorithm analysis, data structures (Fibonacci heaps), pseudorandom number generation, and as benchmarks for recursion and optimization techniques.

First 20 Fibonacci Numbers
n	F(n)	n	F(n)
0	0	10	55
1	1	11	89
2	1	12	144
3	2	13	233
4	3	14	377
5	5	15	610
6	8	16	987
7	13	17	1,597
8	21	18	2,584
9	34	19	4,181

Growth Rate

Fibonacci numbers grow exponentially—roughly as the golden ratio φ ≈ 1.618 raised to the power n:

F(n) ≈ φⁿ / √5 where φ = (1 + √5) / 2 ≈ 1.618

This means F(n) roughly multiplies by 1.618 with each increment of n. By F(45), we're already at over a billion. By F(93), we exceed what a 64-bit integer can hold.

The Naive Recursive Implementation

The recursive definition of Fibonacci translates directly into code. It's almost irresistible in its elegance—and this is precisely the trap.

fibonacci-naive.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
/**
 * Naive recursive Fibonacci - EXTREMELY INEFFICIENT!
 * 
 * Mathematical definition:
 *   F(0) = 0
 *   F(1) = 1
 *   F(n) = F(n-1) + F(n-2) for n ≥ 2
 * 
 * WARNING: Time complexity is O(2^n) - exponential!
 * Do NOT use this for n > 35 or so.
 */
function fib(n: number): number {
    // Base cases
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Recursive case: TWO recursive calls!
    return fib(n - 1) + fib(n - 2);
}
 
// Test it
console.log(fib(10)); // 55 - fast
console.log(fib(20)); // 6765 - still okay
console.log(fib(30)); // 832040 - getting slow...
console.log(fib(40)); // 102334155 - VERY slow!
// fib(50) - don't even try, will take minutes to hours

Why Is This So Slow?

The code is only 8 lines. It directly mirrors the mathematical definition. It works. And yet, computing fib(50) would take longer than you'd ever want to wait.

The problem is the branching factor. Unlike factorial which makes one recursive call, Fibonacci makes two. Each of those makes two more. The call tree explodes exponentially.

Let's trace fib(5) to see what's happening:

Converting Mermaid diagram...

Observe the repetition:

fib(3) is computed 2 times
fib(2) is computed 3 times
fib(1) is computed 5 times
fib(0) is computed 3 times

For just fib(5), we make 15 function calls to compute a value that could be found in a simple table lookup! The same subproblems are solved over and over again.

Exponential Explosion

For fib(n), the number of function calls is approximately 2^n. This means:

• fib(30): ~1 billion calls • fib(40): ~1 trillion calls • fib(50): ~1 quadrillion calls

Even at a million calls per second, fib(50) would take over 30 years. This is the price of not recognizing overlapping subproblems.

Understanding Overlapping Subproblems

The phenomenon we've observed has a name: overlapping subproblems. This is one of the two key properties that define problems suitable for dynamic programming (the other being optimal substructure).

Definition

Overlapping subproblems occur when a recursive algorithm solves the same subproblem multiple times. Instead of each recursive call working on a unique piece of the problem (like factorial), the same sub-computations appear repeatedly across different branches of the recursion tree.

Visualizing the Overlap

Consider fib(6). Here's how many times each subproblem is computed:

Subproblem Computation Count for fib(6)
Subproblem	Times Computed	Wasted Computations
fib(6)	1	0 (root)
fib(5)	1	0
fib(4)	2	1
fib(3)	3	2
fib(2)	5	4
fib(1)	8	7
fib(0)	5	4

The pattern in the "Times Computed" column is itself Fibonacci! This isn't coincidental—it's a deep structural property of the recursion tree.

Why Does This Happen?

Overlapping subproblems arise when:

Multiple paths lead to the same subproblem — In fib(6), both fib(5) and fib(4) need fib(3)
The subproblem space is polynomial — There are only n+1 unique Fibonacci values from 0 to n
The recursion tree is exponential — But we're computing a polynomial number of unique values

The mismatch between exponential calls and polynomial unique subproblems is the signature of overlapping subproblems.

Recognizing Overlapping Subproblems

Ask yourself: "Does my recursive function get called with the same arguments multiple times?" If yes, you have overlapping subproblems. A function with parameters (i, j) has overlapping subproblems if the same (i, j) pair appears multiple times across different execution paths.

Contrast with Factorial

Factorial does not have overlapping subproblems:

factorial(5) calls factorial(4)
factorial(4) calls factorial(3)
Each value from 5 down to 0 is computed exactly once
No overlap means linear time O(n)

Fibonacci has massive overlap:

fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) is computed by both fib(5) and fib(4)
This branching creates exponential redundancy

The difference is single recursion (factorial) vs. multiple recursion (Fibonacci) where the recursive calls share sub-subproblems.

Time Complexity of Naive Fibonacci

Let's rigorously analyze the time complexity of the naive recursive Fibonacci.

Recurrence Relation

Let T(n) be the number of operations to compute fib(n):

T(0) = 1                      (base case)
T(1) = 1                      (base case)
T(n) = T(n-1) + T(n-2) + c    (recursive case: two calls plus constant work)

Notice something remarkable: T(n) has the same recurrence structure as F(n)! The time to compute F(n) grows at the same rate as F(n) itself.

Lower Bound: O(φⁿ)

Since T(n) ≥ F(n) (we do at least as many operations as the final value), and F(n) ≈ φⁿ/√5, we have:

T(n) = Ω(φⁿ) ≈ Ω(1.618ⁿ)

This is exponential—not quite O(2ⁿ), but close to O(1.618ⁿ).

Upper Bound: O(2ⁿ)

For an upper bound, observe that T(n) ≤ 2T(n-1) + c (since T(n-2) < T(n-1)):

T(n) ≤ 2·T(n-1) + c ≤ 2ⁿ·c

So T(n) = O(2ⁿ)

Tight Bound

The precise bound is T(n) = Θ(φⁿ) where φ ≈ 1.618, the golden ratio.

Exponential Growth: Operations for Naive fib(n)
n	F(n)	Approximate Calls	Time @ 10⁹ ops/sec
10	55	~177	< 1 μs
20	6,765	~21,891	< 1 ms
30	832,040	~2.7 million	~3 ms
40	102,334,155	~331 million	~0.3 sec
50	12,586,269,025	~40 billion	~40 sec
60	1,548,008,755,920	~5 trillion	~1.5 hours
100	3.5 × 10²⁰	~1 × 10²¹	~32,000 years

Exponential Time is Brutal

Each increment of n multiplies the work by ~1.618. Going from n=50 to n=100 doesn't take twice as long—it takes billions of times longer. This is why recognizing exponential algorithms and knowing how to optimize them is critical.

Space Complexity

The space complexity is better: O(n).

Why? Because the recursion goes down at most n levels before hitting a base case. Even though the total number of calls is exponential, they don't all exist on the stack simultaneously. The maximum stack depth is proportional to n.

This is a common pattern: exponential time but polynomial space, because the recursion tree is wide (exponential branches) but not exceptionally deep (polynomial depth).

Memoization: Caching Recursive Results

The fix for overlapping subproblems is conceptually simple: don't recompute what you've already computed. Store the result of each unique subproblem the first time you solve it, and return the stored result if you encounter the same subproblem again.

This technique is called memoization (not "memorization"—it comes from "memo," as in making a note of something).

fibonacci-memoized.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
/**
 * Memoized recursive Fibonacci - EFFICIENT!
 * 
 * Uses a cache (memo) to store previously computed values.
 * Each unique subproblem is solved only once.
 * 
 * Time Complexity: O(n) - each subproblem computed once
 * Space Complexity: O(n) - for memo and call stack
 */
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
    // Check if already computed
    if (memo.has(n)) {
        return memo.get(n)!;  // Cache hit - return stored result
    }
    
    // Base cases
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Recursive case: compute and cache
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, result);  // Store for future use
    
    return result;
}
 
// Now it's lightning fast!
console.log(fibMemo(10));   // 55 - instant
console.log(fibMemo(50));   // 12586269025 - still instant!
console.log(fibMemo(100));  // 354224848179262000000 - instant!
 
// Alternative: closure-based memoization
function createMemoizedFib(): (n: number) => number {
    const memo = new Map<number, number>();
    
    function fib(n: number): number {
        if (memo.has(n)) return memo.get(n)!;
        if (n === 0) return 0;
        if (n === 1) return 1;
        
        const result = fib(n - 1) + fib(n - 2);
        memo.set(n, result);
        return result;
    }
    
    return fib;
}
 
const fib = createMemoizedFib();
console.log(fib(100)); // Works instantly

How Memoization Works

Before computing: Check if we've already solved this subproblem
If cached: Return the stored result immediately (O(1) lookup)
If not cached: Compute the result recursively, then store it before returning
Result: Each unique subproblem is solved exactly once

The Transformation

With memoization, the recursion tree effectively collapses:

Converting Mermaid diagram...

The blue nodes represent cache hits—subproblems that return immediately without further recursion. Instead of 15 calls for fib(5), we make only 9. The savings grow dramatically with n.

Exponential → Linear

Memoization transforms:

• Time: O(2ⁿ) → O(n) • Space: O(n) → O(n) (unchanged, but now includes memo storage)

This is one of the most dramatic algorithmic improvements possible—from effectively impossible to trivially fast.

Bottom-Up Dynamic Programming

Memoization is top-down dynamic programming: we start with the big problem, recursively break it down, and cache results. There's an alternative approach: bottom-up dynamic programming.

Instead of starting at fib(n) and working down, we start at fib(0) and build up to fib(n). This eliminates recursion entirely.

fibonacci-bottom-up.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
/**
 * Bottom-up iterative Fibonacci
 * 
 * Builds the solution from smallest subproblems upward.
 * No recursion - purely iterative.
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(n) for dp array, or O(1) if optimized
 */
function fibBottomUp(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // dp[i] will store F(i)
    const dp: number[] = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    // Build solution from bottom up
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}
 
/**
 * Space-optimized bottom-up Fibonacci
 * 
 * Observation: We only need the last two values!
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(1) - just two variables!
 */
function fibOptimized(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    let prev2 = 0;  // F(i-2)
    let prev1 = 1;  // F(i-1)
    
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
console.log(fibBottomUp(50));   // 12586269025
console.log(fibOptimized(50));  // 12586269025 - same but O(1) space

Top-Down (Memoization)

•Starts with target problem
•Recursive + caching
•Only computes needed subproblems
•Easier to derive from recurrence
•Has function call overhead

Bottom-Up (Tabulation)

•Starts with base cases
•Iterative + table filling
•Computes all subproblems up to n
•May be harder to visualize dependencies
•No recursion overhead, often faster

The Space Optimization Insight

Notice that to compute F(n), we only need F(n-1) and F(n-2). We don't need F(n-3) or earlier—they've already been used and combined into more recent values. This observation reduces space from O(n) to O(1). This pattern of"rolling" or "sliding window" optimization appears in many DP problems.

Choosing the Right Approach

We now have four ways to compute Fibonacci:

Naive recursion — O(2ⁿ) time, O(n) space — Never use
Memoized recursion — O(n) time, O(n) space — Good
Bottom-up DP — O(n) time, O(n) space — Good
Space-optimized iterative — O(n) time, O(1) space — Best

For Fibonacci specifically, the space-optimized iterative solution is clearly best. But the lessons generalize to more complex problems where the choice isn't as obvious.

When to Use Each Dynamic Programming Approach
Situation	Recommended Approach	Reason
Exploring the problem / prototyping	Top-down memoization	Easier to write; mirrors the recurrence
Need only specific subproblems	Top-down memoization	Avoids computing unnecessary subproblems
Need all subproblems anyway	Bottom-up tabulation	Slightly faster; no recursion overhead
Space is critical	Bottom-up with rolling array	Often reducible to O(1) or O(row) space
Complex dependency order	Top-down memoization	Don't need to figure out correct fill order
Production code / maximum performance	Bottom-up tabulation	Typically fastest after optimization

The Fibonacci Sequence Beyond Computing

Fibonacci isn't just a recursion example—it's a fundamental pattern. It appears in:

• Analysis of Euclidean algorithm (worst case inputs are consecutive Fibonacci numbers) • Fibonacci heaps (a sophisticated data structure) • Worst-case analysis of AVL trees • Financial modeling and trading algorithms • DNA sequences and biological patterns

Understanding Fibonacci deeply pays dividends across computer science.

Summary: The Overlapping Subproblems Pattern

Fibonacci has taught us one of the most important lessons in algorithmic thinking: when multiple recursive calls create overlapping subproblems, naive recursion becomes exponentially slow, but this can be fixed with caching.

Key Takeaways

•Fibonacci makes two recursive calls — This branching creates an exponential explosion of redundant computation
•Overlapping subproblems occur when the same sub-computation appears multiple times across different recursion paths
•Naive recursion is O(2ⁿ) — Practically useless for n > 40
•Memoization (top-down DP) caches results, reducing to O(n) time and space
•Bottom-up DP (tabulation) builds solutions iteratively from base cases
•Space optimization recognizes that only recent values are needed, achieving O(1) space
•This pattern is the gateway to dynamic programming — a technique that transforms many exponential algorithms into polynomial ones

What's Next

We've seen linear recursion (factorial) and branching recursion with overlap (Fibonacci). Next, we'll explore binary recursion more broadly—patterns where a function makes two recursive calls on distinct (non-overlapping) subproblems. This leads us toward the powerful divide and conquer paradigm, where splitting problems in half yields elegant logarithmic and O(n log n) algorithms.

Page Complete

You now understand why Fibonacci is the canonical example of overlapping subproblems, how memoization transforms exponential into linear complexity, and the foundations of dynamic programming. This knowledge will be essential as you encounter DP problems in graphs, strings, and optimization.

2 / 4

Loading learning content...

Data Structures & AlgorithmsRecursion

Common Recursive Patterns

LevelIntermediate

Duration60 mins

TopicRecursion

2 / 4

Fibonacci and Overlapping Subproblems

When Recursion Becomes Expensive

What You Will Learn

The Fibonacci Sequence

The Fibonacci sequence is one of the most famous sequences in mathematics, appearing in nature, art, architecture, and computer science. It's defined as:

F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n ≥ 2

The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Each number is the sum of the two before it:

F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8

This simple rule generates a sequence with remarkable mathematical properties.

Fibonacci in Nature and Computing

First 20 Fibonacci Numbers
n	F(n)	n	F(n)
0	0	10	55
1	1	11	89
2	1	12	144
3	2	13	233
4	3	14	377
5	5	15	610
6	8	16	987
7	13	17	1,597
8	21	18	2,584
9	34	19	4,181

Growth Rate

Fibonacci numbers grow exponentially—roughly as the golden ratio φ ≈ 1.618 raised to the power n:

F(n) ≈ φⁿ / √5 where φ = (1 + √5) / 2 ≈ 1.618

This means F(n) roughly multiplies by 1.618 with each increment of n. By F(45), we're already at over a billion. By F(93), we exceed what a 64-bit integer can hold.

The Naive Recursive Implementation

The recursive definition of Fibonacci translates directly into code. It's almost irresistible in its elegance—and this is precisely the trap.

fibonacci-naive.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
/**
 * Naive recursive Fibonacci - EXTREMELY INEFFICIENT!
 * 
 * Mathematical definition:
 *   F(0) = 0
 *   F(1) = 1
 *   F(n) = F(n-1) + F(n-2) for n ≥ 2
 * 
 * WARNING: Time complexity is O(2^n) - exponential!
 * Do NOT use this for n > 35 or so.
 */
function fib(n: number): number {
    // Base cases
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Recursive case: TWO recursive calls!
    return fib(n - 1) + fib(n - 2);
}
 
// Test it
console.log(fib(10)); // 55 - fast
console.log(fib(20)); // 6765 - still okay
console.log(fib(30)); // 832040 - getting slow...
console.log(fib(40)); // 102334155 - VERY slow!
// fib(50) - don't even try, will take minutes to hours

Why Is This So Slow?

The code is only 8 lines. It directly mirrors the mathematical definition. It works. And yet, computing fib(50) would take longer than you'd ever want to wait.

The problem is the branching factor. Unlike factorial which makes one recursive call, Fibonacci makes two. Each of those makes two more. The call tree explodes exponentially.

Let's trace fib(5) to see what's happening:

Converting Mermaid diagram...

Observe the repetition:

fib(3) is computed 2 times
fib(2) is computed 3 times
fib(1) is computed 5 times
fib(0) is computed 3 times

For just fib(5), we make 15 function calls to compute a value that could be found in a simple table lookup! The same subproblems are solved over and over again.

Exponential Explosion

For fib(n), the number of function calls is approximately 2^n. This means:

• fib(30): ~1 billion calls • fib(40): ~1 trillion calls • fib(50): ~1 quadrillion calls

Even at a million calls per second, fib(50) would take over 30 years. This is the price of not recognizing overlapping subproblems.

Understanding Overlapping Subproblems

Definition

Visualizing the Overlap

Consider fib(6). Here's how many times each subproblem is computed:

Subproblem Computation Count for fib(6)
Subproblem	Times Computed	Wasted Computations
fib(6)	1	0 (root)
fib(5)	1	0
fib(4)	2	1
fib(3)	3	2
fib(2)	5	4
fib(1)	8	7
fib(0)	5	4

The pattern in the "Times Computed" column is itself Fibonacci! This isn't coincidental—it's a deep structural property of the recursion tree.

Why Does This Happen?

Overlapping subproblems arise when:

Multiple paths lead to the same subproblem — In fib(6), both fib(5) and fib(4) need fib(3)
The subproblem space is polynomial — There are only n+1 unique Fibonacci values from 0 to n
The recursion tree is exponential — But we're computing a polynomial number of unique values

The mismatch between exponential calls and polynomial unique subproblems is the signature of overlapping subproblems.

Recognizing Overlapping Subproblems

Contrast with Factorial

Factorial does not have overlapping subproblems:

factorial(5) calls factorial(4)
factorial(4) calls factorial(3)
Each value from 5 down to 0 is computed exactly once
No overlap means linear time O(n)

Fibonacci has massive overlap:

fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) is computed by both fib(5) and fib(4)
This branching creates exponential redundancy

The difference is single recursion (factorial) vs. multiple recursion (Fibonacci) where the recursive calls share sub-subproblems.

Time Complexity of Naive Fibonacci

Let's rigorously analyze the time complexity of the naive recursive Fibonacci.

Recurrence Relation

Let T(n) be the number of operations to compute fib(n):

T(0) = 1                      (base case)
T(1) = 1                      (base case)
T(n) = T(n-1) + T(n-2) + c    (recursive case: two calls plus constant work)

Notice something remarkable: T(n) has the same recurrence structure as F(n)! The time to compute F(n) grows at the same rate as F(n) itself.

Lower Bound: O(φⁿ)

Since T(n) ≥ F(n) (we do at least as many operations as the final value), and F(n) ≈ φⁿ/√5, we have:

T(n) = Ω(φⁿ) ≈ Ω(1.618ⁿ)

This is exponential—not quite O(2ⁿ), but close to O(1.618ⁿ).

Upper Bound: O(2ⁿ)

For an upper bound, observe that T(n) ≤ 2T(n-1) + c (since T(n-2) < T(n-1)):

T(n) ≤ 2·T(n-1) + c ≤ 2ⁿ·c

So T(n) = O(2ⁿ)

Tight Bound

The precise bound is T(n) = Θ(φⁿ) where φ ≈ 1.618, the golden ratio.

Exponential Growth: Operations for Naive fib(n)
n	F(n)	Approximate Calls	Time @ 10⁹ ops/sec
10	55	~177	< 1 μs
20	6,765	~21,891	< 1 ms
30	832,040	~2.7 million	~3 ms
40	102,334,155	~331 million	~0.3 sec
50	12,586,269,025	~40 billion	~40 sec
60	1,548,008,755,920	~5 trillion	~1.5 hours
100	3.5 × 10²⁰	~1 × 10²¹	~32,000 years

Exponential Time is Brutal

Space Complexity

The space complexity is better: O(n).

This is a common pattern: exponential time but polynomial space, because the recursion tree is wide (exponential branches) but not exceptionally deep (polynomial depth).

Memoization: Caching Recursive Results

This technique is called memoization (not "memorization"—it comes from "memo," as in making a note of something).

fibonacci-memoized.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
/**
 * Memoized recursive Fibonacci - EFFICIENT!
 * 
 * Uses a cache (memo) to store previously computed values.
 * Each unique subproblem is solved only once.
 * 
 * Time Complexity: O(n) - each subproblem computed once
 * Space Complexity: O(n) - for memo and call stack
 */
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
    // Check if already computed
    if (memo.has(n)) {
        return memo.get(n)!;  // Cache hit - return stored result
    }
    
    // Base cases
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Recursive case: compute and cache
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, result);  // Store for future use
    
    return result;
}
 
// Now it's lightning fast!
console.log(fibMemo(10));   // 55 - instant
console.log(fibMemo(50));   // 12586269025 - still instant!
console.log(fibMemo(100));  // 354224848179262000000 - instant!
 
// Alternative: closure-based memoization
function createMemoizedFib(): (n: number) => number {
    const memo = new Map<number, number>();
    
    function fib(n: number): number {
        if (memo.has(n)) return memo.get(n)!;
        if (n === 0) return 0;
        if (n === 1) return 1;
        
        const result = fib(n - 1) + fib(n - 2);
        memo.set(n, result);
        return result;
    }
    
    return fib;
}
 
const fib = createMemoizedFib();
console.log(fib(100)); // Works instantly

How Memoization Works

Before computing: Check if we've already solved this subproblem
If cached: Return the stored result immediately (O(1) lookup)
If not cached: Compute the result recursively, then store it before returning
Result: Each unique subproblem is solved exactly once

The Transformation

With memoization, the recursion tree effectively collapses:

Converting Mermaid diagram...

The blue nodes represent cache hits—subproblems that return immediately without further recursion. Instead of 15 calls for fib(5), we make only 9. The savings grow dramatically with n.

Exponential → Linear

Memoization transforms:

• Time: O(2ⁿ) → O(n) • Space: O(n) → O(n) (unchanged, but now includes memo storage)

This is one of the most dramatic algorithmic improvements possible—from effectively impossible to trivially fast.

Bottom-Up Dynamic Programming

Memoization is top-down dynamic programming: we start with the big problem, recursively break it down, and cache results. There's an alternative approach: bottom-up dynamic programming.

Instead of starting at fib(n) and working down, we start at fib(0) and build up to fib(n). This eliminates recursion entirely.

fibonacci-bottom-up.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
/**
 * Bottom-up iterative Fibonacci
 * 
 * Builds the solution from smallest subproblems upward.
 * No recursion - purely iterative.
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(n) for dp array, or O(1) if optimized
 */
function fibBottomUp(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // dp[i] will store F(i)
    const dp: number[] = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    // Build solution from bottom up
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}
 
/**
 * Space-optimized bottom-up Fibonacci
 * 
 * Observation: We only need the last two values!
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(1) - just two variables!
 */
function fibOptimized(n: number): number {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    let prev2 = 0;  // F(i-2)
    let prev1 = 1;  // F(i-1)
    
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
console.log(fibBottomUp(50));   // 12586269025
console.log(fibOptimized(50));  // 12586269025 - same but O(1) space

Top-Down (Memoization)

•Starts with target problem
•Recursive + caching
•Only computes needed subproblems
•Easier to derive from recurrence
•Has function call overhead

Bottom-Up (Tabulation)

•Starts with base cases
•Iterative + table filling
•Computes all subproblems up to n
•May be harder to visualize dependencies
•No recursion overhead, often faster

The Space Optimization Insight

Choosing the Right Approach

We now have four ways to compute Fibonacci:

Naive recursion — O(2ⁿ) time, O(n) space — Never use
Memoized recursion — O(n) time, O(n) space — Good
Bottom-up DP — O(n) time, O(n) space — Good
Space-optimized iterative — O(n) time, O(1) space — Best

For Fibonacci specifically, the space-optimized iterative solution is clearly best. But the lessons generalize to more complex problems where the choice isn't as obvious.

When to Use Each Dynamic Programming Approach
Situation	Recommended Approach	Reason
Exploring the problem / prototyping	Top-down memoization	Easier to write; mirrors the recurrence
Need only specific subproblems	Top-down memoization	Avoids computing unnecessary subproblems
Need all subproblems anyway	Bottom-up tabulation	Slightly faster; no recursion overhead
Space is critical	Bottom-up with rolling array	Often reducible to O(1) or O(row) space
Complex dependency order	Top-down memoization	Don't need to figure out correct fill order
Production code / maximum performance	Bottom-up tabulation	Typically fastest after optimization

The Fibonacci Sequence Beyond Computing

Fibonacci isn't just a recursion example—it's a fundamental pattern. It appears in:

Understanding Fibonacci deeply pays dividends across computer science.

Summary: The Overlapping Subproblems Pattern

Key Takeaways

•Fibonacci makes two recursive calls — This branching creates an exponential explosion of redundant computation
•Overlapping subproblems occur when the same sub-computation appears multiple times across different recursion paths
•Naive recursion is O(2ⁿ) — Practically useless for n > 40
•Memoization (top-down DP) caches results, reducing to O(n) time and space
•Bottom-up DP (tabulation) builds solutions iteratively from base cases
•Space optimization recognizes that only recent values are needed, achieving O(1) space
•This pattern is the gateway to dynamic programming — a technique that transforms many exponential algorithms into polynomial ones

What's Next

Page Complete

2 / 4