# History of recursion

Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?

• This question may be too broad: "the impact of recursion on computer science"? Also, a more specific title to the question would be nice. Commented Aug 18, 2010 at 17:47

Computability and Recursion, by Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

This paper is the first of the history of computation papers available here: http://www.people.cs.uchicago.edu/~soare/History/

• Section 2.2 is titled "The Origin of Recursion." Commented Aug 18, 2010 at 17:37
• It's interesting to see this mathematical account of the history of recursion. I confused this question for a history of the concept of recusion, which has undoubtedly been a mainstay of human thought for at least as far back as we have good literature. Commented Aug 18, 2010 at 17:46
• See also Soare's article in "Handbook of Computability Theory", 1999. Commented Nov 1, 2010 at 0:47
• Could someone please explain the joke to this befuddled non-native speaker? According to Google, "recusion" is (1) a misspelling of "recursion", or (2) an Arthur&Aston bag brand-name. Or is it supposed to be connected to "cusion" somehow? Or to "cuss"? Commented Nov 7, 2015 at 13:06
• @Emil, it is a Google Easter Egg that the search for recursion refers to the search page itself. Commented Nov 7, 2015 at 14:44

Not the first, but important so far as the practical application is concerned: "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" by John McCarthy (in which he introduced Lisp)

Maybe slightly tangential to the original question, but the blog entry "How recursion got into programming: a comedy of errors" describes an interesting part of early computing history.

From Recursive Functions article on SEP:

The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of natural number. In logic, recursion appears in Skolem [1923], where it is noted that many basic functions can be defined by simple applications of the method. The modern formalisation and development of the notion is due to a number of people, most notably Gödel [1931], Herbrand, Rózsa Péter [1951] and Kleene [1936]. Kleene in 1952 described Péter as “the leading contributor to the special theory of recursive functions”. She presented a paper on the recursive functions at the International Congress of Mathematicians in Zurich in 1932.