Cover photo by Sebastian Alvarez on Unsplash

Previously, on "Iteration"...

I introduced the concept of iteration by way of a whimsical allegory about counting a staircase. To count the steps of a staircase, we first came up with a practical definition of what the "length" of a staircase is:

The length of a staircase can be described as the value of the first stair, plus the length of the rest of the staircase.

We then used that definition to derive an intuitive algorithm for calculating staircase length:

When counting the steps of a staircase, if you're at the top, stop counting.
Otherwise, add 1 to the result of counting the rest of the staircase.

My implementation of that algorithm showcased the elegance of recursion, which deconstructs a problem into a composition of the solutions to its parts. And we saw that recursion lends itself well to wholistic computation, i.e. situations in which you only care about the final result.

Constructive iteration

Today, I want to talk about other ways of approaching iteration that might lend themselves better to constructive computation. I'm using the term constructive in the mathematical sense, which I just learned about recently and think fits this topic particularly well.

A constructive process, in my mind, is one that gives you insight into the progress of the computation it is performing.

To keep with the "staircase traversal" imagery from my previous discussion of iteration, I imagine a constructive traversal of a staircase to be one in which, after each step, you know exactly how many you've climbed.

It's like you're actually building the staircase as you go, keeping track of how many steps you've added so far. Once you've decided to stop, you already know exactly how many steps are in the staircase without further computation.

We-Who-Code often refer to this type of iteration as looping, which captures the idea that each step you take closes a 'loop' in a larger 'circuit' of computation.

When looping, you can stop at the end of any step without worrying so much about unfinished work: if you stop precisely at the "end" of your computation, your record-keeping will reflect the solution to the whole thing; on the other hand, if you stop early, you'll still have something to show for it, it might just be an approximation of the result you were driving towards.

How many stairs are in a staircase?

So: how do you count the stairs of a staircase like this?

The basic algorithm is the same: climb until you reach the top, tracking each step you take.

The difference in implementation is in the way you track your steps: instead of waiting to evaluate the sum once you've reached the top, you evaluate as you go.

Our recursive implementation of #count-stairs from last time looked like this:

As we saw, this builds up a single computation by keeping a tally of the steps you've climbed and evaluates it once you've reached the top. For example, calling this version of #count-stairs with a staircase of four steps would build and evaluate an expression like this:

With only a slight modification, this 'non-constructive' iteration can become constructive. Let's give it a try.

If we want to keep track of how many steps we've taken at every step we take, we need a place to store that information. So the first thing to do is introduce a variable to hold the result of that computation: let's call it tally.

Since tally will hold the number of stairs we've stepped, and the number of stairs we've stepped is precisely the length of the staircase we've climbed, we now want to return our tally once we reach the top.

Finally, we add the current step to our tally and count the rest of the staircase.

This new way of 'counting the rest' is the key to an implementation that evaluates the tally as it counts, rather than deferring evaluation of the tally to when counting has stopped.

Putting it all together, our new #count-stairs function looks like this:

Quite similar to the original, no?

💡 This form of recursion is often called 'tail recursion', because the "do it again" part happens at the tail-end of the loop, and no more computation is done in the same loop.

To anyone who writes code, I highly recommend the book Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman. This section in particular is a great resource on the topics I'm discussing here.

What I find fascinating is how the shape of the computation changes with just these few simple modifications. Taking again a staircase of four steps to illustrate our algorithm, our computation diagram now looks something more like this:

Do you see the staircase we're climbing? 😄

Loop constructs

Iteration is useful and loops prevalent. We-Who-Code even apply the concept of iteration to applying the concept of iteration.

But depending on the tools you're using, repeatedly calling the same function isn't the only way to loop.

Many languages provide explicit "loop constructs" we can use in situations where a recursive function call may negatively impact how well our code communicates our intent to other humans and machines.

There are also times where it may not be the most mechanically efficient one, either; see SICP for a brief discussion on the performance of various compilers with respect to handling iterative code patterns.

Since these constructs are language-specific, I won't go into much more detail than to mention a few names they are commonly given, to aid you in your quest to better know your tools:

• for
• while
• until
• loop
• each
• do-while

---

Every tool has its use. Some can make your code clearer to humans or clearer to machines, and some can strike a bit of balance between both.

"Good enough to work" should not be "good enough for you." Hold yourself to a higher standard: learn a little about a lot and a lot about a little, so that when the time comes to do something, you've got a fair idea of how to do it well.