Examples of Recursion: The Good, the Bad, and the Silly

What we need: a really good example

The programming artefact of recursion, also known as “writing a subroutine that calls itself”, is well known to generations of students of computer science. Recursion is a reasonably simple yet a remarkably powerful concept. That is, it’s a reasonably simple concept once you understand it, but unfortunately, it can take some effort to get that understanding.

Teachers of computer science are faced with the challenge of finding good examples of recursive programs to offer to their students. The ideal example will demonstrate the principle of recursion clearly while hinting at its power, and thus show why it’s a compelling concept. Over the years I have come across examples of recursive programs, enough now that I think I can classify them into three broad categories: the good, the bad, and the silly. Here are the categories, each with an example:

The Good: Towers of Hanoi

Towers of Hanoi is a puzzle that consists of three posts, and a set of disks of different sizes with holes in the middle so that the disks can be stacked on the posts. You start with all disks stacked on one post, ranging from smallest to largest, top to bottom. Your job is to transfer the stack from the first post to the third, using the second post for temporary storage. You can only move one disk at a time, and you can never place a larger disk on top of a smaller disk.

The puzzle can be solved easily by breaking down the job into smaller jobs. To move the entire stack of disks from the first to the third post, do these steps:

• Move the (slightly smaller) stack of all but the largest disk from the first to the second post,
• Then move the largest disk from the first post to the third,
• Then move the (slightly smaller) stack from the second to the third post.

The middle task is a simple step – just move one disk – but the first and last steps each require solving again the Towers of Hanoi puzzle but for a smaller stack. In other words, solving the full puzzle requires solving two simpler instances of the puzzle.

Why are C’s Pointers and Arrays Confused?

C Arrays and C Pointers

One thing that always confuses is people learning the C programming language is the duality between arrays and pointers. In your C program you might create an array, which is a block of storage:

Then when you call a subroutine with the array as a parameter, the array magically transforms into a pointer to itself:

You are taught that array definitions are different from pointer definitions:

Except in places where they aren’t:

Now, when you were first learning the C programming language, you probably asked yourself: why do arrays and pointers have this confusing relationship; why can’t arrays just be arrays and a pointers just be pointers? (Or maybe you didn’t ask yourself. While studying programming, perhaps you have come to believe that computer languages are by nature complex and arcane things full of unknowable mysteries, and that true programmers have skills that are a cross between those of tax accountants and Harry Potter. And all this stuff about arrays and pointers merely reinforces your belief.) Well, it turns out there is a reason why arrays and pointers act as they do, and this reason is rooted in the history of the C programming language.

The Language that Came Before C

When Dennis Richie at Bell Labs designed the C programming language in the early 1970s, he based it on another language named B, which had been designed by colleague Ken Thompson.

A program written in B would be reasonably legible to a C programmer because B is essentially a simpler version of C. The most notable difference between B and C is that B is a typeless language, that is, variables do not have explicit data types like character or integer. Or, rather, there is exactly one data type: the machine word, which is equivalent to C’s integer type ‘int’.

Now you might think that working with things like character strings would be difficult when your only data type is int, but B provides some help. For example, characters treated as small integers (e.g., ‘A’ is identical to 65), and a string is an array of words with four characters packed per word. To work with the characters in a string, you use the library functions char( string, index ) and lchar( string, index, replacement ).

Arrays are a problem because you obviously cannot pack an array into a single machine word. B solves this problem by defining an array to be a pointer to a block of storage, and having program code deal with the pointer, which does fit in a word. This means that when you define an array, B sets aside storage for both the array itself and the pointer to it:

When you work with an array in B, you are always working with the pointer. This makes it straightforward to pass an array to a subroutine: you pass the pointer to the block of storage unchanged, and both the caller and callee work with the same thing, namely that pointer. This also keeps B’s calling mechanism simple: parameters are always passed by value with no danger of trying to copy blocks of storage into subroutines.

C Tries to Keep Things Tidy

With C came a full suite of data types including arrays as fully-fledged objects. This has advantages, for example, the program does not create pointers unnecessarily, and multi-dimensional arrays are easy to build. However there is a downside when calling subroutines. Because C passes parameters by value, passing an array to a subroutine theoretically means copying the entire array into the subroutine. Not only is copying a block of storage expensive for all but the tiniest of arrays, it is generally not a useful thing for a program to do.

There are a couple of ways around this call-by-value-with-arrays issue, but both involve additional syntax. One way is to allow both call-by-value and call-by-reference parameters in subroutine calls. C++, for example, supports both modes; programmers can select call-by-reference by adding an “&” to the parameter declaration. Another way is to require the programmer to explicitly generate pointers to arrays and pass them into the subroutine, but this requires the programmer to clutter the subroutine code with dereferencing “*” operators.

With C, Ritchie tried to find a middle ground by designing a mechanism for subroutine calls that normally uses the traditional call-by-value, but automatically switches to call-by-reference for arrays. This solves the call-by-value-with-arrays problem and avoids explicit syntax for call-by-reference parameters. This permitted C to deliver the benefits of arrays as first-class objects, while offering a familiar, uncluttered syntax to B programmers (and to Fortran programmers as well) who were migrating to C.

This design fix, with what might be called “hidden dereferencing”, has proven effective in routine program code. It is when a programmer wanders off the beaten path that hidden dereferences can come out hiding and bite not only students but also professional programmers.

Back to the Future with Java

Other languages like Pascal, which appeared around the same time as C, and C++ support both call-by-reference and call-by-value parameter-passing modes with explicit syntax to distinguish the two (“var” and “&”, respectively). Interestingly, Java, a language of more recent design, goes back to B’s idea of always using references (i.e., pointers) to deal with objects.

Although Java’s object references — whereby you always work with references to objects  rather than directly with the objects themselves — echoes the array pointers of B, Java’s references are more sophisticated than B’s pointers. B programmers had to worry about memory leakage (a block of memory with no pointer to it), dangling pointers (a pointers referring to a block of memory that has been deallocated), and other such horrors. Java has tamed the wild pointers of B through built-in mechanisms such as garbage collection and automatic array-bounds checking.