3

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.

  • 2
    Does assembly language count? – Ixrec Oct 31 '15 at 11:23
  • OK, so you could implement recursion in assembly, and other early languages, but the programmer had to do the heavy lifting. What was the first language where a developer could simply self-invoke a function and have the computer handle the invocations and subsequent unwindings? – Ben Oct 31 '15 at 11:29
  • 2
    Recursion in assembly is no more difficult than calling another function in assembly, provided you store the local data on a stack rather than in a pre-allocated memory segment. While old Fortran and Cobol disallowed recursion, Lisp ('58) and Algol ('60) certainly supported it. – amon Oct 31 '15 at 11:51
  • A history tag should be added to this post. – dbasnett Oct 31 '15 at 11:54
  • 2
    I believe LISP-58 was first implemented in 1960. I don't know if that version supported recursion, or if it did it may have had problems. McCarthy began his work on garbage collection to address some of those problems around the same time. A lot of roads lead to and from Project MAC at MIT in the early 60's. – dbasnett Oct 31 '15 at 12:08
10

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.

LISP prehistory - Summer 1956 through Summer 1958

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).

The implementation of LISP

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.

  • 1
    If we are talking compiled languages ALGOL-60 is the clear winner. I think it was '64 before there was a LISP compiler available. – dbasnett Oct 31 '15 at 15:04
3

ALGOL-60 by Dijkstra and Zonneveld. Recursion was not part of the original specification, but Dijkstra insisted.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.