Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?
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/
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.
The use of recursion goes back to the 19th century. Dedekind  used the notion to obtain functions needed in his formal analysis of the concept of natural number. In logic, recursion appears in Skolem , 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 , Herbrand, Rózsa Péter  and Kleene . 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.
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.