Implementing algorithms in terms of iterators

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...