História de recursão

14

Quem introduziu a ideia de recursão ?
Alguém pode explicar de onde veio e como afetou a ciência da computação?

Srinivas Reddy Thatiparthy
fonte
5
Essa questão pode ser muito ampla: "o impacto da recursão na ciência da computação"? Além disso, um título mais específico para a pergunta seria bom.
Shane

Respostas:

19

Computabilidade e Recursão, da Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

Este artigo é o primeiro da história dos documentos de computação disponíveis aqui: http://www.people.cs.uchicago.edu/~soare/History/

Aaron Sterling
fonte
1
Seção 2.2 é intitulada "A Origem da Recursão".
Aaron Sterling
5
É interessante ver esse relato matemático da história da recursão. Confundi essa pergunta com uma história do conceito de recusão, que sem dúvida foi um dos pilares do pensamento humano, pelo menos desde o início em que temos boa literatura.
Ross Snider
Veja também o artigo de Soare no "Handbook of Computability Theory", 1999.
Kaveh
Alguém poderia, por favor, explicar a piada para esse falante não-nativo confuso? Segundo o Google, "recusão" é (1) um erro de ortografia de "recursão" ou (2) um nome de marca de bolsa Arthur & Aston. Ou deveria estar ligado à "cusion" de alguma forma? Ou para "xingar"?
Emil Jeřábek apoia Monica
1
@Emil, é um ovo de páscoa do Google que a pesquisa por recursão se refere à própria página de pesquisa.
Kaveh
2

Do artigo Funções Recursivas no SEP :

O uso da recursão remonta ao século XIX. Dedekind [1888] usou a noção para obter funções necessárias em sua análise formal do conceito de número natural. Na lógica, a recursão aparece em Skolem [1923], onde se observa que muitas funções básicas podem ser definidas por aplicações simples do método. A formalização e o desenvolvimento modernos da noção são devidos a várias pessoas, principalmente Gödel [1931], Herbrand, Rózsa Péter [1951] e Kleene [1936]. Kleene, em 1952, descreveu Péter como "o principal colaborador da teoria especial das funções recursivas". Ela apresentou um artigo sobre as funções recursivas no Congresso Internacional de Matemáticos em Zurique em 1932.

Ele sugere o seguinte para obter mais informações:

Em particular, consulte a seção intitulada " As primeiras definições recursivas " na página 5.

Kaveh
fonte
1

Não sei quando surgiu, mas a solução recursiva para as Torres de Hanói é freqüentemente usada como exemplo introdutório. O problema se originou antes de abordagens formais em computação.

Rafael
fonte
2
Na verdade não. As Torres de Hanói foram inventadas por Edouard Lucas em 1883, muito depois das primeiras abordagens formais de cálculo de Babbage e Ada Lovelace (seu artigo foi publicado em 1843).
Jeffrey Shallit