The Advent of Recursion in Programming, 1950s-1960s
Edgar G. Daylight
Abstract:
The term `recursive' has had different meanings during the past two
centuries among various communities of scholars. Its historical
epistemology has already been described by Soare (1996) with respect
to the mathematicians, logicians, and recursive-function
theorists. The computer practitioners, on the other hand, are
discussed in this paper by focusing on the definition and
implementation of the ALGOL60 programming language. Recursion entered
ALGOL60 in two novel ways: (i) syntactically with what we now call BNF
notation, and (ii) dynamically by means of the recursive procedure. As
is shown, both (i) and (ii) were introduced by linguistically-inclined
programmers who were not versed in logic and who, rather
unconventionally, abstracted away from the down-to-earth
practicalities of their computing machines. By the end of the 1960s,
some computer practitioners had become aware of the theoretical
insignificance of the recursive procedure in terms of computability,
though without relying on recursive-function theory. The presented
results help us to better understand the technological ancestry of
modern-day computer science, in the hope that contemporary researchers
can more easily build upon its past.