The story of recursion

Recently I’ve read a fascinating, well researched article on how recursion got into mainstream programming — or, more specifically, into ALGOL 60, from which many contemporary languages descend from. It made me realize three things:

1. Activation record allocation was once static.
2. Recursion is hard to avoid.
3. You can circumvent design by committee.

Let’s have a detailed look at each of these.

Activation record allocation was once static

Every function¹ needs some space to store its local variables and passed parameters when it’s called. This space is called its activation record.

Today, activation records are usually organized into a stack that grows and shrinks as needed. But in the 50’s, it was apparently common to allocate activation records statically. There was just one pre-allocated record for each function. This obviously meant that each function could be active only once, prohibiting recursion.

Allowing recursion meant switching from static activation record allocation to a dynamic, stack-based one. It was controversial at the time (presumably because it had performance and complexity implications), and it was the main reason why some people resisted adding recursion into ALGOL 60 at the time.

Somehow, I always thought that the stack and functions came together. Apparently, they did not.

Recursion is hard to avoid

It’s really hard to prevent recursion when you have functions. First, you need to prohibit direct recursion by not allowing functions to call themselves in their bodies. Next, you need to analyze the call graph at compile-time to detect instances of indirect recursion (alternatively, you can just disallow forward function declarations). But the real trouble starts when you introduce pointers to functions. Once you have them, recursion can sneak in by passing a pointer as a parameter somewhere. It can’t be checked statically anymore.

If you don’t want to have recursion in your language, you have to do work, and even then, it’s a futile battle. To me, this suggests that recursion is a natural concept (for some definition of natural). If a language has functions, recursion should be allowed.

You can circumvent design by committee

The ALGOL 60 language was specified in a document called the ALGOL 60 Report. It was produced by a committee, yet it was an example of a compact and elegant text. This is not usually the case. How was that possible?

It turns out that the committee was circumvented by one determined individual — Peter Naur. He consolidated ALGOL design discussion that was happening at the time, produced a draft of the ALGOL 60 Report just before the final design conference, and handed it out to its attendees. Because the confernece’s limited time span, they didn’t have much choice but to accept this draft as the basis of discussion.

As Friedrich L. Bauer (member of the design group) recalls:

Peter Naur had not been commissioned to do so, it was a fait accompli. It therefore sounds poetic if he has written that his draft Report was ‘chosen’ as the basis of the discussion; the Committee was simply forced to do so, after Peter Naur had gained this advantage.

After the conference, Peter Naur became the editor of the report, and kept it under control.

This example shows it is possible to get good results even in the presence of a committee. All it takes is a capable individual taking over the work and maneuvering the committee into a position where the easiest and most reasonable course of action is to go with what this individual proposes.

I have to admit I’ve used variations on this strategy few times at SUSE. It usually worked, and sometimes the “committee” didn’t even realize it was circumvented.

Conclusion

To get the full picture of the recursion story, I can only recommend you to read the article yourself. And big thanks to Ladislav Thon for making me notice it via a retweet.