What was the first programming language to support convenient user-land recursion?
I know that early languages did not support it, but can find no specifics on when it was introduced.
Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.Sign up to join this community
One of the design goals of Lisp was to support recursion. John McCarthy, the designer of Lisp, writes in his History of Lisp:
I spent the summer of 1958 at the IBM Information Research Department at the invitation of Nathaniel Rochester and chose differentiating algebraic expressions as a sample problem. […] In fact, the differentiation program was not implemented that summer, because FLPL [ed: a Fortran dialect] allows neither conditional expressions nor recursive use of subroutines. At this point a new language was necessary, since […] neither conditional expressions nor recursion could be implemented with machine language Fortran functions - not even with “functions” that modify the code that calls them.
The implementation of LISP began in Fall 1958. […]
[…] Anyway, I decided to write a paper describing LISP both as a programming language and as a formalism for doing recursive function theory. The paper was Recursive functions of symbolic expressions and their computation by machine, part I (McCarthy 1960).
Lisp and Algol were designed in parallel and were aware of each other. For example, if-then-else was proposed by McCarthy for Algol-58 and included in Algol-60. Later Lisps borrowed heavily from Algol. So it's a bit difficult to tell which came first – while the idea behind Lisp including recursion seems to be older than that idea in Algol 60, actual Algol 60 compilers were already available in 1960, well before the first complete Lisp compiler of 1962. However, it seems that Steve Russell implemented Lisp via the
eval interpreter function in 1958, although good references are hard to come by.
It seems fair to say that Lisp and in Algol-60 were published at approximately the same time, even though the Lisp language is generally dated to 1958, not to 1960. In general, Lisp is considered to be the second high-level language after Fortran, predating Cobol and Algol.
In any case, Lisp took many ideas including explicit support for recursion from the 1956 Information Processing Language, an assembly-style list processing language.