DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

Back to Recursion

Fibonacci Sequence Recursion

See the explosive growth of naive recursion vs the efficiency of memoization in computing Fibonacci numbers.

Exponential vs Linear

O(2^n) vs O(n)

Memoization Magic

Controls

Fibonacci Number (n): 5

fib(5) = 5

Algorithm Mode:

🔥 Recalculating everything from scratch

Speed: 800ms

Performance Stats

Current calls:0

Naive total:15

Memoized total:6

Speedup: 3x faster with memoization!

Current Step

Step 1 of 0

Click Start to begin the Fibonacci visualization

Current Call:

Call Tree VisualizationNAIVE

Click Start to see the call tree in action

Python Implementation

def fibonacci_naive(n):
    # Base case
    if n <= 1:
        return n
    
    # Recursive case - exponential time!
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

def fibonacci_memo(n, memo={}):
    # Check cache first
    if n in memo:
        return memo[n]
    
    # Base case
    if n <= 1:
        memo[n] = n
        return n
    
    # Compute and cache result
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# Example: fib(5) = 5
# Naive calls: 15 vs Memoized calls: 6

JavaScript Implementation

function fibonacciNaive(n) {
    if (n <= 1) return n;
    return fibonacciNaive(n-1) + fibonacciNaive(n-2);
}

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) {
        memo[n] = n;
        return n;
    }
    memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo);
    return memo[n];
}

// Example: fib(5) = 5

Algorithm Analysis

Naive Recursion

• Time: O(2^n) - exponential growth
• Space: O(n) - recursion depth
• Calls: 15 for fib(5)
• Recalculates same values repeatedly
• Becomes unusably slow for n > 35

With Memoization

• Time: O(n) - linear time
• Space: O(n) - cache + recursion
• Calls: 6 for fib(5)
• Each value computed only once
• Dramatically faster for large n

Real-World Applications

• Nature: Flower petals, spiral shells, bee genealogy
• Finance: Elliott wave theory, market analysis
• Computer Science: Algorithm analysis, golden ratio
• Art/Design: Golden rectangle, architectural proportions
• Biology: DNA structure, population growth models
• Optimization: Dynamic programming introduction

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

Back to Recursion

Fibonacci Sequence Recursion

See the explosive growth of naive recursion vs the efficiency of memoization in computing Fibonacci numbers.

Exponential vs Linear

O(2^n) vs O(n)

Memoization Magic

Controls

Fibonacci Number (n): 5

fib(5) = 5

Algorithm Mode:

🔥 Recalculating everything from scratch

Speed: 800ms

Performance Stats

Current calls:0

Naive total:15

Memoized total:6

Speedup: 3x faster with memoization!

Current Step

Step 1 of 0

Click Start to begin the Fibonacci visualization

Current Call:

Call Tree VisualizationNAIVE

Click Start to see the call tree in action

Python Implementation

def fibonacci_naive(n):
    # Base case
    if n <= 1:
        return n
    
    # Recursive case - exponential time!
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

def fibonacci_memo(n, memo={}):
    # Check cache first
    if n in memo:
        return memo[n]
    
    # Base case
    if n <= 1:
        memo[n] = n
        return n
    
    # Compute and cache result
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# Example: fib(5) = 5
# Naive calls: 15 vs Memoized calls: 6

JavaScript Implementation

function fibonacciNaive(n) {
    if (n <= 1) return n;
    return fibonacciNaive(n-1) + fibonacciNaive(n-2);
}

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) {
        memo[n] = n;
        return n;
    }
    memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo);
    return memo[n];
}

// Example: fib(5) = 5

Algorithm Analysis

Naive Recursion

• Time: O(2^n) - exponential growth
• Space: O(n) - recursion depth
• Calls: 15 for fib(5)
• Recalculates same values repeatedly
• Becomes unusably slow for n > 35

With Memoization

• Time: O(n) - linear time
• Space: O(n) - cache + recursion
• Calls: 6 for fib(5)
• Each value computed only once
• Dramatically faster for large n

Real-World Applications

• Nature: Flower petals, spiral shells, bee genealogy
• Finance: Elliott wave theory, market analysis
• Computer Science: Algorithm analysis, golden ratio
• Art/Design: Golden rectangle, architectural proportions
• Biology: DNA structure, population growth models
• Optimization: Dynamic programming introduction