Fibonacci is usually introduced as "the next term is the sum of the two previous terms" (sometimes with the story about rabbits or whatever). There's two obviou

Fibonacci is usually introduced as "the next term is the sum of the two previous terms" (sometimes with the story about rabbits or whatever). There's two obvious ways to implement this: 1. Direct recursion 2. Keep track of the two previous terms If you start with (1), you run it and it takes exponential time, and so you should instead remember the two previous terms, leading you to (2). When you go with (2), you either use 2 mutable variables and a loop in the imperative version, or you have 2 accumulators and tail recursion in the functional version... which is the same thing, since a tail recursive function is just a named loop. There's nothing about laziness or self-referencing an incomplete structure here, which is just a Haskell thing. Taking the tail of an incomplete structure, in particular, is indirect and hard to understand. If you want to demonstrate laziness, you can still do it directly by doing something like: fibs a b = a : fibs b (a + b) fib n = fibs 0 1 !! n