Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?
$\begingroup$
$\endgroup$
1
asked Aug 18, 2010 at 17:27
-
5$\begingroup$ This question may be too broad: "the impact of recursion on computer science"? Also, a more specific title to the question would be nice. $\endgroup$– ShaneAug 18, 2010 at 17:47
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
6
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/
answered Aug 18, 2010 at 17:36
-
1$\begingroup$ Section 2.2 is titled "The Origin of Recursion." $\endgroup$ Aug 18, 2010 at 17:37
-
5$\begingroup$ 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. $\endgroup$ Aug 18, 2010 at 17:46
-
$\begingroup$ See also Soare's article in "Handbook of Computability Theory", 1999. $\endgroup$– KavehNov 1, 2010 at 0:47
-
$\begingroup$ 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"? $\endgroup$ Nov 7, 2015 at 13:06
-
1$\begingroup$ @Emil, it is a Google Easter Egg that the search for recursion refers to the search page itself. $\endgroup$– KavehNov 7, 2015 at 14:44
$\begingroup$
$\endgroup$
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)
$\begingroup$
$\endgroup$
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.
answered Nov 7, 2015 at 13:53
$\begingroup$
$\endgroup$
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:
- Rod Adams, "An Early History of Recursive Functions and Computability from Gödel to Turing", 2011.
In particular see the section titled "The First Recursive Definitions" on page 5.
$\begingroup$
$\endgroup$
1
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.
-
2$\begingroup$ 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). $\endgroup$ Nov 7, 2015 at 15:10