Iterators usually iterate by moving their position from one item of a container to another. But they do not necessarily need to iterate over data structures at all. Iterators can also be used to implement algorithms, in which case, they would calculate the next value when they are incremented (++it) and return that value when they are dereferenced (*it).

In this section, we demonstrate this by implementing the Fibonacci function in form of an iterator. The Fibonacci function is recursively defined like this: F(n) = F(n - 1) + F(n - 2). It starts with the beginning values of F(0) = 0 and F(1) = 1. This leads to the following number sequence:

• F(0) = 0
• F(1) = 1
• F(2) = F(1) + F(0) = 1
• F(3) = F(2) + F(1) = 2
• F(4) = F(3) + F(2) = 3
• F(5) = F(4) + F(3) = 5
• F(6) = F(5) + F(4) = 8
• ... and so on

If we implement this in the form of a callable function that returns the Fibonacci value for any number, n, we will end up with a recursive self-calling function, or a loop implementation. This is fine, but what if we write some program where have to consume Fibonacci numbers in some pattern, one after the other? We would have two possibilities--either we recalculate all the recursive calls for every new Fibonacci number, which is a waste of computing time, or we save the last two Fibonacci numbers as temporary variables and use them to calculate the next. In the latter case, we reimplemented the Fibonacci algorithm loop implementation. It seems that we would end up mixing Fibonacci code with our actual code, which solves a different problem:

size_t a {0};
size_t b {1};

for (size_t i {0}; i < N; ++i) {
    const size_t old_b {b};
    b += a;
    a  = old_b;
    
    // do something with b, which is the current fibonacci number
}

Iterators are an interesting way out of this. How about wrapping the steps that we do in the loop-based iterative Fibonacci implementation in the prefix increment ++ operator implementation of a Fibonacci value iterator? This is pretty easy, as this section demonstrates.