Problem Description

This problem asks you to implement a generator function that produces the Fibonacci sequence infinitely.

The Fibonacci sequence follows the mathematical relation: Xₙ = Xₙ₋₁ + Xₙ₋₂, where each number is the sum of the two preceding numbers.

The sequence starts with 0 and 1, and continues as: 0, 1, 1, 2, 3, 5, 8, 13, ...

Your task is to create a generator function fibGenerator() that:

• Returns a generator object
• When calling next() on the generator, it yields the next number in the Fibonacci sequence
• The generator should be able to produce Fibonacci numbers indefinitely

For example:

• First call to gen.next().value returns 0
• Second call to gen.next().value returns 1
• Third call to gen.next().value returns 1
• Fourth call to gen.next().value returns 2
• And so on...

The solution uses two variables a and b to track the current and next Fibonacci numbers. Initially, a = 0 and b = 1. In each iteration:

1. Yield the current value a
2. Update the values using array destructuring: [a, b] = [b, a + b], which simultaneously sets a to the old value of b and b to the sum of old a and b

This approach maintains constant space complexity while generating the sequence infinitely.

Intuition

The key insight is recognizing that we only need to keep track of the last two numbers in the sequence to generate the next one. Since the Fibonacci formula Xₙ = Xₙ₋₁ + Xₙ₋₂ only depends on the two most recent values, we don't need to store the entire sequence.

Think of it like climbing stairs where each step depends on where your two feet were previously positioned. You don't need to remember every step you've taken - just where your feet are now.

We start with the base cases: the first two Fibonacci numbers are 0 and 1. These serve as our initial "two feet" positions.

To generate each subsequent number:

• The current number to output is always the smaller of our two stored values
• The next number in our pair is always the sum of our current two values
• We slide our "window" forward by replacing the smaller value with the larger one, and the larger value with their sum

The generator function is perfect for this problem because:

1. We need to produce values on-demand rather than all at once
2. The sequence is potentially infinite
3. Each value depends only on the previous state, making it ideal for maintaining state between yield statements

The elegant array destructuring [a, b] = [b, a + b] performs the "sliding window" update in one line. This simultaneously moves b into a's position and calculates the new b as a + b, using the original values before any assignment happens.

Solution Approach

The implementation uses a generator function with JavaScript's function* syntax to create an infinite sequence producer.

State Management: We maintain two variables:

• a: Stores the current Fibonacci number to be yielded
• b: Stores the next Fibonacci number in the sequence

Initially, we set a = 0 and b = 1, representing the first two numbers of the Fibonacci sequence.

The Infinite Loop: The while (true) loop ensures our generator can produce values indefinitely. This is safe because generators are lazy - they only compute values when explicitly requested via next().

Core Algorithm Steps:

1. Yield Current Value: yield a pauses execution and returns the current Fibonacci number
2. State Update: [a, b] = [b, a + b] performs the critical update:
   • The new a becomes the old b
   • The new b becomes the sum of old a and old b
   • This happens atomically using destructuring assignment

Example Walkthrough:

Initial: a = 0, b = 1
Call 1: yield 0, then a = 1, b = 0 + 1 = 1
Call 2: yield 1, then a = 1, b = 1 + 1 = 2
Call 3: yield 1, then a = 2, b = 1 + 2 = 3
Call 4: yield 2, then a = 3, b = 2 + 3 = 5
Call 5: yield 3, then a = 5, b = 3 + 5 = 8

TypeScript Type Annotations: The function signature Generator<number, any, number> indicates:

• number: The type of values yielded
• any: The return type (not used since it runs infinitely)
• number: The type of values that can be passed to next() (not used in this implementation)

This approach achieves O(1) space complexity and O(1) time complexity per generated number, making it highly efficient for on-demand Fibonacci number generation.

Example Walkthrough

Let's trace through the generator function to see how it produces the first 5 Fibonacci numbers:

Initial Setup:

const gen = fibGenerator();
// Internal state: a = 0, b = 1

First call - gen.next():

• Current state: a = 0, b = 1
• Yield a → returns 0
• Update: [a, b] = [b, a + b] → [a, b] = [1, 0 + 1] → a = 1, b = 1

Second call - gen.next():

• Current state: a = 1, b = 1
• Yield a → returns 1
• Update: [a, b] = [b, a + b] → [a, b] = [1, 1 + 1] → a = 1, b = 2

Third call - gen.next():

• Current state: a = 1, b = 2
• Yield a → returns 1
• Update: [a, b] = [b, a + b] → [a, b] = [2, 1 + 2] → a = 2, b = 3

Fourth call - gen.next():

• Current state: a = 2, b = 3
• Yield a → returns 2
• Update: [a, b] = [b, a + b] → [a, b] = [3, 2 + 3] → a = 3, b = 5

Fifth call - gen.next():

• Current state: a = 3, b = 5
• Yield a → returns 3
• Update: [a, b] = [b, a + b] → [a, b] = [5, 3 + 5] → a = 5, b = 8

Sequence generated: 0, 1, 1, 2, 3, ...

Notice how we only ever store two numbers at a time. The variable a always holds the current Fibonacci number to output, while b holds the next one in line. The destructuring assignment elegantly slides our two-number window forward through the infinite sequence.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) per next() call

Each call to next() performs a constant amount of work:

• One yield operation
• One array destructuring assignment [a, b] = [b, a + b]
• Two additions and two assignments

Since these operations don't depend on the size of any input or the number of previous calls, each iteration has constant time complexity.

Space Complexity: O(1)

The generator maintains only two variables a and b to track the current and next Fibonacci numbers, regardless of how many times next() is called. The space usage remains constant throughout the generator's lifetime. The temporary array [b, a + b] created during destructuring is also constant size and doesn't grow with the number of iterations.

Common Pitfalls

1. Integer Overflow for Large Fibonacci Numbers

The most critical pitfall is that Fibonacci numbers grow exponentially. After generating around 90-100 numbers, the values can exceed the maximum safe integer limit in many programming languages. In JavaScript, this limit is Number.MAX_SAFE_INTEGER (2^53 - 1), and in Python, while integers can grow arbitrarily large, this can lead to performance degradation and memory issues.

Solution:

• In JavaScript/TypeScript, use BigInt for large Fibonacci numbers:

function* fibGenerator() {
    let a = 0n, b = 1n;
    while (true) {
        yield a;
        [a, b] = [b, a + b];
    }
}

• In Python, be aware of memory consumption for very large numbers and consider implementing a maximum limit or using modular arithmetic if only remainders are needed:

def fibGenerator(max_value=None):
    current, next_num = 0, 1
    while True:
        if max_value and current > max_value:
            return  # Stop generation when limit is reached
        yield current
        current, next_num = next_num, current + next_num

2. Forgetting to Store the Generator Object

A common mistake is calling the generator function multiple times instead of storing the generator object:

# Wrong - creates new generator each time
fibGenerator().__next__()  # 0
fibGenerator().__next__()  # 0 (always returns first value)

# Correct - store and reuse the generator
gen = fibGenerator()
next(gen)  # 0
next(gen)  # 1

3. Attempting to Iterate Backwards or Reset

Generators are forward-only iterators. Once a value is consumed, you cannot go back or reset without creating a new generator instance. Developers might expect to reset or rewind the sequence.

Solution: If you need to access previous values or reset, consider:

• Creating a new generator instance
• Implementing a class-based approach with reset functionality:

class FibonacciGenerator:
    def __init__(self):
        self.reset()
  
    def reset(self):
        self.current = 0
        self.next_num = 1
  
    def get_next(self):
        value = self.current
        self.current, self.next_num = self.next_num, self.current + self.next_num
        return value

4. Memory Issues When Collecting All Values

Trying to convert an infinite generator to a list will cause memory exhaustion:

# DON'T DO THIS - will run forever and crash
all_fibs = list(fibGenerator())

# Instead, use itertools.islice for a specific range
from itertools import islice
first_10_fibs = list(islice(fibGenerator(), 10))