# What was the first language to support convenient user-land recursion?

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.

• 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
• 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
• 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

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.

• 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

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