Case study: 165.998% efficiency increase?

[Kreyren]

Initial

#[inline]
fn fibonacci(n: u64) -> u64 {
    match n {
        0 => 1,
        1 => 1,
        n => fibonacci(n-1) + fibonacci(n-2),
    }
}

This is by 99.99% MORE efficient compared to previous

fn fibonacci(n: u64) -> u64 {
    let mut a = 0;
    let mut b = 1;

    match n {
        0 => b,
        _ => {
            for _ in 0..n {
                let c = a + b;
                a = b;
                b = c;
            }
            b
        }
    }
}

Where this is +165.998% MORE efficient compared to initial (+65.988% compared to previous)

fn fibonacci() -> impl Iterator<Item = u128> {
    let mut state = [1, 1];
    std::iter::from_fn(move || {
        state.rotate_left(1);
        let next = state[0] + state[1];
        Some(std::mem::replace(&mut state[1], next))
    })
}

Iterators don't actually do anything if their .next() method isn't called. The .take() method creates a new iterator that limits itself to the first n items of the original iterator, but its .next() ultimately calls through to the original iterator. -- rustlang discord

Relevant: https://doc.rust-lang.org/stable/std/iter/#laziness

---

Why?