How to follow recursion with lazy sequences
Recursion is often the most difficult programming concept to become comfortable with. Add laziness and it can make it hard to even understand what’s going on. Stepping through examples is great practice for really grasping these fundamental concepts.
In Programming Clojure, the authors give a nice, concise (though admittedly inefficient) definition of a Fibonacci sequence:
The execution detail is hard to follow, so let’s step through to see what’s happening.
The first thing to do is understand what
…yields a Seqable object that will invoke the body only the first time seq is called
In other words, the args you pass to
lazy-seq won’t be evaluated until they are needed.
So let’s work out the first couple of simple steps:
take 1, the
0N of the first
lazy-seq suffices and we don’t need to further evaluate, we get the value
take 2 is similar, in that the first
lazy-seq suffices by providing two values, giving
take 3 gives us a more interesting case:
Now, the first
lazy-seq only satisfies 2 out of the 3 values needed, so we process the next
Since we need one more value, we map over the first value of each
That gives us our final value of
(0N 1N 1N).
Becoming comfortable with recursion and laziness takes time and practice, but it DOES become second nature if you’re willing. And soon, you’ll find yourself writing more elegant code with fewer bugs.