<p>Not the first, but important so far as the practical application is concerned: <a href="http://www-formal.stanford.edu/jmc/recursive.pdf">"Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"</a> by John McCarthy (in which he introduced Lisp)</p>

CC BY-SA 2.5
2010-08-18T17:39:36.540Z
2010-08-18T17:39:36.540Z
Shane
<p>From <a href="http://plato.stanford.edu/entries/recursive-functions/" rel="nofollow">Recursive Functions</a> article on <a href="http://plato.stanford.edu/" rel="nofollow">SEP</a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>It suggest the following for more information:</p>

<ul>
<li>Rod Adams, "<a href="https://books.google.ca/books?id=G9YoeRIVSnwC" rel="nofollow">An Early History of Recursive Functions and Computability from Gödel to Turing</a>", 2011.</li>
</ul>

<p>In particular see the section titled "<a href="https://books.google.ca/books?id=G9YoeRIVSnwC&amp;lpg=PP1&amp;pg=PA5" rel="nofollow">The First Recursive Definitions</a>" on page 5.</p>

CC BY-SA 3.0
2015-11-07T14:38:00.953Z
2015-11-07T14:38:00.953Z
Kaveh
<p>Maybe slightly tangential to the original question, but the blog entry "<a href="https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/" rel="nofollow">How recursion got into programming: a comedy of errors</a>" describes an  interesting part of early computing history.</p>

CC BY-SA 3.0
2015-11-07T13:53:40.677Z
2015-11-07T13:53:40.677Z
Martin Berger
<p>I do not know when it came up, but the <a href="http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution" rel="nofollow">recursive solution for Towers of Hanoi</a> is frequently used as introductory example. The problem originated before formal approaches on computation.</p>

CC BY-SA 3.0
2015-11-07T15:10:26.607Z
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
CC BY-SA 2.5
2010-11-01T08:31:47.463Z
2010-11-01T08:31:47.463Z
Raphael
<p>Computability and Recursion, by Soare.
<a href="http://www.people.cs.uchicago.edu/~soare/History/compute.pdf">http://www.people.cs.uchicago.edu/~soare/History/compute.pdf</a></p>

<p>This paper is the first of the history of computation papers available here:
<a href="http://www.people.cs.uchicago.edu/~soare/History/">http://www.people.cs.uchicago.edu/~soare/History/</a></p>

CC BY-SA 3.0
2015-11-07T13:06:42.270Z
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
CC BY-SA 3.0
2015-11-07T14:44:11.677Z
@Emil, it is a Google Easter Egg that the search for recursion refers to the search page itself.
Kaveh
CC BY-SA 3.0
2015-11-07T14:51:16.553Z
@Kaveh It does indeed, but how is that connected to Ross Snider's "recusion" joke?
Emil Jeřábek
CC BY-SA 2.5
2010-11-01T00:47:02.567Z
See also Soare's article in "Handbook of Computability Theory", 1999.
Kaveh
CC BY-SA 2.5
2010-08-18T17:37:46.463Z
Section 2.2 is titled "The Origin of Recursion."
Aaron Sterling
CC BY-SA 2.5
2010-08-18T17:46:35.670Z
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
CC BY-SA 2.5
2010-08-18T17:36:29.213Z
2010-08-18T17:36:29.213Z
Aaron Sterling
<p>Who introduced the idea of <a href="https://en.wikipedia.org/wiki/Recursion" rel="nofollow">recursion</a>?<br>
Can someone explain where it came from and how it impacted computer science?</p>

CC BY-SA 2.5
2010-08-18T17:47:31.580Z
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
<reference-request><ho.history-overview><recursion>
History of recursion
Srinivas Reddy Thatiparthy
# History of recursion

(Asked by: username_0 on 2010-08-18)

Who introduced the idea of [recursion](https://en.wikipedia.org/wiki/Recursion)?  
Can someone explain where it came from and how it impacted computer science?

**Tags:** reference-request, ho.history-overview, recursion
> **Comments:**
> **username_1**: This question may be too broad: "the impact of recursion on computer science"?  Also, a more specific title to the question would be nice.  

---

## 5 answers

### Answer by username_6 on 2010-08-18. Score: 19 | Accepted answer

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

> **Comments:**
> **username_6**: Section 2.2 is titled "The Origin of Recursion."  
> **username_8**: 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.  
> **username_2**: See also Soare's article in "Handbook of Computability Theory", 1999.  
> **username_7**: 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"?  
> **username_2**: @Emil, it is a Google Easter Egg that the search for recursion refers to the search page itself.  
> **username_7**: @Kaveh It does indeed, but how is that connected to Ross Snider's "recusion" joke?  

---

### Answer by username_1 on 2010-08-18. Score: 6

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"](http://www-formal.stanford.edu/jmc/recursive.pdf) by John McCarthy (in which he introduced Lisp)


---

### Answer by username_2 on 2015-11-07. Score: 3

From [Recursive Functions](http://plato.stanford.edu/entries/recursive-functions/) article on [SEP](http://plato.stanford.edu/):

> 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](https://books.google.ca/books?id=G9YoeRIVSnwC)", 2011.

In particular see the section titled "[The First Recursive Definitions](https://books.google.ca/books?id=G9YoeRIVSnwC&lpg=PP1&pg=PA5)" on page 5.


---

### Answer by username_3 on 2015-11-07. Score: 3

Maybe slightly tangential to the original question, but the blog entry "[How recursion got into programming: a comedy of errors](https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/)" describes an interesting part of early computing history.


---

### Answer by username_4 on 2010-11-01. Score: 1

I do not know when it came up, but the [recursive solution for Towers of Hanoi](http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution) is frequently used as introductory example. The problem originated before formal approaches on computation.

> **Comments:**
> **username_5**: 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).  

---

