# 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. – Shane Aug 18 '10 at 17:47

## 5 Answers

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." – Aaron Sterling Aug 18 '10 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. – Ross Snider Aug 18 '10 at 17:46
• See also Soare's article in "Handbook of Computability Theory", 1999. – Kaveh Nov 1 '10 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"? – Emil Jeřábek Nov 7 '15 at 13:06
• @Emil, it is a Google Easter Egg that the search for recursion refers to the search page itself. – Kaveh Nov 7 '15 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.

It suggest the following for more information:

In particular see the section titled "The First Recursive Definitions" on page 5.

I do not know when it came up, but the recursive solution for Towers of Hanoi is frequently used as introductory example. The problem originated before formal approaches on computation.

• Not really. The Towers of Hanoi were invented by Edouard Lucas in 1883, which is rather long after the first formal approaches to calculation by Babbage and Ada Lovelace (her paper was published in 1843). – Jeffrey Shallit Nov 7 '15 at 15:10