How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics | A Programmers Place

A Programmers Place

Observations, Reviews, and Essays

" Dijkstra, Blaauw, and the origin of computer architecture

Recursion versus iteration "

How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics

By now it is difficult to imagine that once there was a time when the utility, and even the possibility, of recursion in programming was in doubt. Yet that was true of the programming community around 1960. Even the committee that was to create Algol 60 was divided on the issue. How recursion got into the language is a story of intrigue and misunderstandings. I came across this story for the first time when reading Gauthier van den Hove’s excellent MSc thesis [11]. It is also the subject of Chapter 3 in [12].

In the late 1950s a committee was formed to design a universal, machine-independent programming language. Such a language was not a superfluous luxury at the time: programmers were using programming systems provided by the hardware manufacturers that were not even uniform across the different models. Fortran was the first exception, but was at the time still tied to a single manufacturer. Lisp was a harbinger of things to come: machine-independent and not tied to a manufacturer. This is what Algol wanted to be, but then more official: sponsored by IFIP, the International Federation for Information Processing, established under the auspices of UNESCO.

McCarthy, fresh from the success of his Lisp project, was enthusiastic about recursion as an elegant way to get computers to do what they are best at: repeat execution of the same code with suitable modification each time around. In fact, the first Lisp had no iteration, so that the only way to add all elements of a linear list was to write a recursively defined function. As a member of the Algol committee he proposed making the possibility of recursion a feature of the new language. The proposal was crowded out by more pressing concerns. The result was that in the early months of 1960, when the report was to be finalized, there was no consensus on recursion.

There were plenty of reasons to be opposed. It was not clear whether it could be implemented: a flaky academic experiment like the Lisp interpreter was not an authoritative example for the solid, efficient compiler that the German faction of the committee had in mind. But committee members Naur and van Wijngaarden agreed with McCarthy that recursion was too tempting an opportunity to be missed. Van Wijngaarden had been egged on by his sidekick Edsger W. Dijkstra, who was in favour of recursion and who may well have supplied van Wijngaarden with his new, as yet unpublished, ideas about implementing recursion.

Naur was the committee member editing the final version of the Algol report. Two decades later Naur remembered it as follows [1]:

The last substantial change of language concepts was the admission of recursive procedure activations. This took place as follows. […] [O]n about February 10, […] I had a telephone call from A. van Wijngaarden, speaking also for E.W. Dijkstra. They pointed to an important lack of definition in the draft report, namely the meaning, if any, of an occurrence of a procedure identifier inside the body of the declaration other than in the left part of an assignment. They also made it clear that preventing recursive activations through rules of the description would be complicated because of the possibilities of indirect activation through procedures and their parameters. They proposed to clarify the matter by adding a sentence to section 5.4.4.: "Any other occurrence of the procedure identifier within the procedure body denotes activation of the procedure." I got charmed with the boldness and simplicity of this suggestion and decided to follow it in spite of the risk of subsequent trouble over the question.

It turned out that there was "trouble over the question". Several committee members had been tricked into approving a final version of the report that included an easily overlooked late addition that settled the controversy in the direction opposite to their wish. Committee member F.L. Bauer registered his protest by characterizing the addition of recursion to the language as an "Amsterdam plot" [1, Appendix 5].

That this was not paranoia on the part of Bauer is made clear by Dijkstra in an interview in 2001 [2]:

Recursion was a major step. It was introduced in a sneaky way. The draft ALGOL-60 report was circulated in one of the last weeks of December ’59. We studied it and realized that recursive calls were all but admitted, though it wasn’t stated. And I phoned Peter Naur — that call to Copenhagen was my first international telephone call, I’ll never forget the excitement! — and dictated him one suggestion with the suggestion that he include it. It was something like "Any other...