I decided to go and try again the "elegant" recursive-definition approach, but this time trying to get linear cost. The trick here is modelling Haskell's lazy values in Rust. Although there are great crates for that, I have implemented a sketchy version of it (since all the computations are single-threaded, I have used Rc + RefCell, but of course using Send/Sync wrappers instead would allow it to be usable in a multi-threaded scenario):
fn fib () -> LazyList<u64>
{
// notice the fib instance is shared within the sum.
LazyList![1 ;; 1 ;; { let fib = fib(); fib.tail().clone() + fib }]
}