Tags

, , , , , , , , ,

When it comes to what makes a computer (or any other) language a programming language, there are three characteristics usually required:

  1. Saving state (variables)
  2. Selecting a code path (if-then)
  3. Iteration or recursion (or equivalent)

This post is just a brief note (for a friend) about the third item and why it allows three distinct options.

What’s really going on here is iteration, and given the “or equivalent” option it’s actually debatable whether this really is a requirement of programming languages. The bottom line is that we can accomplish iteration with the first two: state and selection.

The third requirement, if stated only as “Recursion” can be thought of as requiring functions or sub-routines in a programming language. But, again, given the “or equivalent” option, even functions aren’t required in a programming language.

To avoid being coy, the “or equivalent” option refers to labels (that mark a specific point in the code) and the infamous GOTO statement. But since the GOTO is notoriously bad for your health, programmers prefer iteration and/or recursion!

Iteration

It’s almost weird how often code contains sections of one or more statements that need to be repeated over a range of some kind. Maybe it’s a chessboard and we need to clear all the squares or a table of baseball statistics we need to sum.

Many languages offer a hand way to iterate over some sort of range. A common one is the for (or for-next) loop. Here’s a generic example:

data = some-stuff
for ix = 0 to 10
    data = zig(data)
    data = zag(data)
next ix

In this toy example, we have a data thingy, and we want to zig() and zag() over that data ten times. (All we’re doing here is symbolizing repeatedly doing some stuff to some other stuff. And it takes two steps.)

Some languages even provide a nice means of iterating over a list:

data = list-of-some-stuff
for item in data
    zag(zig(item))
next item

(The above assumes we can operate on each item in the list without needing a copy back. That is, we’re directly operating on item. Without that assumption, we’d need a method to put the zig-zagged item back in the data list.)

Without that handy syntax, iterating over a list of stuff is slightly more messy:

data = list-of-some-stuff
for ix in length(data)
    item = data[ix]
    data[ix] = zag(zig(item))
next ix

(At least in this case we no longer need to assume operating directly on the list items. We pull them out, operate on them, and then put them back. It all depends on what we’re doing with the data, and that’s not relevant here.)

Some languages don’t have a for loop (and some situations don’t lend themselves to its use if available), so there is a more basic form of iteration, called a while loop.

data = some-stuff
ix = 0
while ix < 10:
    data = zig(data)
    data = zag(data
    ix = ix + 1

Nearly all languages have a while loop. Some also have an until loop, which is has opposite logic — it loops until some condition becomes true.

Depending on the exact requirements — what we’re doing with the data — there are many variations on the above basic patterns.

One key point here is that, although we used zig() and zag() to stand for some sort of processing of the data, there’s no need for them to be functions. Instead, each of the loops above could contain just a series of code statements. That is to say, we could ‘spell out’ exactly what zig() and zag() actually do.

Given the ability to have variables, selection, and iteration, we have a programming language capable of implementing any algorithm (assuming robust forms of state).

However we can give up the loop constructs in favor of…

Recursion

Every loop above can be implemented as a recursive function. The basic pattern goes something like this:

function stuff_loop (state):
    if done(state):
        return
    do_loop_stuff()
    return stuff_loop(next(state))

The idea is to call the function with some sort of state object that allows two operations: done(), which if true indicates the loop is complete; and next(), which advances to the next state.

The simplest form would be a count-down variable:

function stuff_loop (nbr_times):
    if nbr_times <= 0:
        return
    do_loop_stuff()
    return stuff_loop(n-1)

We often want to pass some data object to the recursion as well as get back a result:

function stuff_loop (nbr_times, data):
    if nbr_times <= 0:
        return data
    data = do_loop_stuff(data)
    return stuff_loop(n-1, data)

And that basically implements the loops above! We us it like this:

data = stuff_loop(10, some-stuff)

Recursively iterating over a list (say to sum a list of numbers) is easy, too (especially if we can consume the list, which makes it its own state object):

function sum_list_of_numbers (list):
    item = remove_first_item(list)
    return item + sum_list_of_numbers(list)

If we can’t consume the list, we need to pass an index (state) variable, just as we did above. We can also use a sum variable:

function sum_list_of_numbers (index, sum, list):
    if length(list) <= index:
        return sum
    item = list[index]
    return sum_list_of_numbers(index+1, sum+item, list)

So anything that can be done with iteration can be done with recursion.

But we don’t actually need either of those if the language provides the ability to label some point in the code (many do) and it has the GOTO statement. These, in fact, are the circumstances under with most compiled code and microprocessors operate.

Or Equivalent

Here’s how we might implement the loop using the crude tools of labels and GOTO statements (we can do this for any of the loops above):

data = some-stuff
ix = 0
:loop_start
if ix < 10:
    zig(data)
    zag(data)
    ix = ix + 1
    goto loop_start

Which is pretty much what any of the loops above might compile down to. Assembly language often lacks loop constructs. (But it does allow sub-routine calls, so loops can be implemented recursively even in assembly.)