Geschichte der Rekursion

14

Wer hat die Idee der Rekursion eingeführt ?
Kann jemand erklären, woher es kommt und wie es sich auf die Informatik auswirkt?

reference-request ho.history-overview recursion Srinivas Reddy Thatiparthy
quelle

5

Diese Frage könnte zu weit gefasst sein: "Der Einfluss der Rekursion auf die Informatik"? Auch ein genauerer Titel zu der Frage wäre schön.

Shane

19

Berechenbarkeit und Rekursion von Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

Dieses Papier ist das erste in der Geschichte der Berechnungspapiere, das hier verfügbar ist: http://www.people.cs.uchicago.edu/~soare/History/

Aaron Sterling
quelle

1

Abschnitt 2.2 trägt den Titel "Der Ursprung der Rekursion".

Aaron Sterling

5

Es ist interessant, diese mathematische Darstellung der Rekursionsgeschichte zu sehen. Ich habe diese Frage für eine Geschichte des Konzepts der Wiederaufnahme verwechselt, das zweifellos ein Grundpfeiler des menschlichen Denkens war, zumindest seit wir über gute Literatur verfügen.

Ross Snider

Siehe auch Soares Artikel in "Handbook of Computability Theory", 1999.

Kaveh

Könnte jemand diesem verwirrten Nicht-Muttersprachler bitte den Witz erklären? Laut Google ist "recusion" (1) ein Rechtschreibfehler von "recursion" oder (2) ein Markenname für Arthur & Aston-Taschen. Oder soll es irgendwie mit "cusion" verbunden sein? Oder "fluchen"?

Emil Jeřábek unterstützt Monica

1

@Emil, es ist ein Google Easter Egg, dass die Suche nach Rekursion auf die Suchseite selbst verweist.

Kaveh

6

Nicht die erste, aber für die praktische Anwendung wichtig: "Rekursive Funktionen symbolischer Ausdrücke und ihre maschinelle Berechnung, Teil I" von John McCarthy (in dem er Lisp vorstellte)

Shane
quelle

2

Vielleicht etwas tangential zur ursprünglichen Frage, aber der Blogeintrag " Wie die Rekursion in die Programmierung kam: eine Komödie der Fehler " beschreibt einen interessanten Teil der frühen Computergeschichte.

Martin Berger
quelle

2

Aus dem Artikel über rekursive Funktionen zu SEP :

Die Verwendung der Rekursion geht auf das 19. Jahrhundert zurück. Dedekind [1888] verwendete den Begriff, um Funktionen zu erhalten, die für seine formale Analyse des Konzepts der natürlichen Zahl benötigt wurden. In der Logik erscheint die Rekursion in Skolem [1923], wo angemerkt wird, dass viele Grundfunktionen durch einfache Anwendungen der Methode definiert werden können. Die moderne Formalisierung und Entwicklung des Begriffs geht auf eine Reihe von Personen zurück, insbesondere auf Gödel [1931], Herbrand, Rózsa Péter [1951] und Kleene [1936]. 1952 beschrieb Kleene Péter als "den führenden Verfasser der speziellen Theorie der rekursiven Funktionen". Sie präsentierte 1932 auf dem Internationalen Mathematikerkongress in Zürich eine Arbeit über die rekursiven Funktionen.

Es wird Folgendes empfohlen, um weitere Informationen zu erhalten:

Rod Adams, " Eine frühe Geschichte rekursiver Funktionen und Berechenbarkeit von Gödel bis Turing ", 2011.

Siehe insbesondere den Abschnitt " Die ersten rekursiven Definitionen " auf Seite 5.

Kaveh
quelle

1

Ich weiß nicht, wann es dazu kam, aber die rekursive Lösung für Türme von Hanoi wird häufig als Einführungsbeispiel verwendet. Das Problem entstand vor formalen Herangehensweisen an die Berechnung.

Raphael
quelle

2

Nicht wirklich. Die Türme von Hanoi wurden 1883 von Edouard Lucas erfunden, was ziemlich lange nach den ersten formalen Berechnungsansätzen von Babbage und Ada Lovelace ist (ihr Aufsatz wurde 1843 veröffentlicht).

Jeffrey Shallit

Geschichte der Rekursion

Antworten: