Histoire de la récursivité

14

Qui a introduit l'idée de récursivité ?
Quelqu'un peut-il expliquer d'où il vient et comment cela a eu un impact sur l'informatique?

reference-request ho.history-overview recursion Srinivas Reddy Thatiparthy
la source
5
Cette question peut être trop large: "l'impact de la récursivité sur l'informatique"? En outre, un titre plus spécifique à la question serait bien.
Shane

Réponses:

19

Calculabilité et récursivité, par Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

Ce document est le premier de l'histoire des documents de calcul disponible ici: http://www.people.cs.uchicago.edu/~soare/History/

Aaron Sterling
la source
1
La section 2.2 est intitulée «L'origine de la récursivité».
Aaron Sterling
5
Il est intéressant de voir ce compte mathématique de l'histoire de la récursivité. J'ai confondu cette question avec une histoire du concept de récession, qui a sans aucun doute été un pilier de la pensée humaine depuis au moins aussi longtemps que nous avons une bonne littérature.
Ross Snider
Voir aussi l'article de Soare dans "Handbook of Computability Theory", 1999.
Kaveh
Quelqu'un pourrait-il expliquer la blague à ce locuteur non natif embrouillé? Selon Google, "recusion" est (1) une faute d'orthographe de "récursivité", ou (2) un nom de marque de sac Arthur & Aston. Ou est-il censé être lié à la "cusion" d'une manière ou d'une autre? Ou pour "cuss"?
Emil Jeřábek soutient Monica
1
@Emil, c'est un œuf de Pâques Google que la recherche de récursivité fait référence à la page de recherche elle-même.
Kaveh
2

De l' article sur les fonctions récursives sur SEP :

L'utilisation de la récursion remonte au 19ème siècle. Dedekind [1888] a utilisé la notion pour obtenir les fonctions nécessaires à son analyse formelle du concept de nombre naturel. En logique, la récursivité apparaît dans Skolem [1923], où il est noté que de nombreuses fonctions de base peuvent être définies par de simples applications de la méthode. La formalisation et le développement modernes de la notion sont dus à un certain nombre de personnes, notamment Gödel [1931], Herbrand, Rózsa Péter [1951] et Kleene [1936]. Kleene en 1952 a décrit Péter comme «le principal contributeur à la théorie spéciale des fonctions récursives». Elle a présenté un article sur les fonctions récursives au Congrès international des mathématiciens à Zurich en 1932.

Il suggère ce qui suit pour plus d'informations:

Voir en particulier la section intitulée « Les premières définitions récursives » à la page 5.

Kaveh
la source
1

Je ne sais pas quand elle est apparue, mais la solution récursive pour Towers of Hanoi est fréquemment utilisée comme exemple d'introduction. Le problème est apparu avant les approches formelles du calcul.

Raphael
la source
2
Pas vraiment. Les tours de Hanoi ont été inventées par Edouard Lucas en 1883, ce qui est assez long après les premières approches formelles du calcul par Babbage et Ada Lovelace (son article a été publié en 1843).
Jeffrey Shallit