Problem Description
Implement a generator function that produces the Fibonacci sequence. The Fibonacci sequence is defined by the recurrence relation X[n] = X[n-1] + X[n-2] with the first two numbers being 0 and 1. Each call to next() on the generator should yield the next number in the sequence.
Key Insights
- Use a generator function to yield sequence values one at a time.
- Maintain state between yields for the last two Fibonacci numbers.
- The problem defines the Fibonacci sequence starting with 0 and 1.
- No need to pre-compute the entire sequence; generate values on the fly.
Space and Time Complexity
Time Complexity: O(n) per call to produce n values. Space Complexity: O(1) since only a constant amount of data is maintained for the state.
Solution
The solution uses a generator function that initializes two variables to represent the first two Fibonacci numbers. In an infinite loop, it yields the current Fibonacci number and then updates the variables to the next numbers in the sequence. This approach minimizes memory usage by only tracking the last two values and relies on Python's lazy evaluation to produce as many Fibonacci numbers as requested.