История рекурсии

14

Кто представил идею рекурсии ?
Может кто-нибудь объяснить, откуда он взялся и как он повлиял на информатику?

Сринивас Редди Татиарти
источник
5
Этот вопрос может быть слишком широким: «влияние рекурсии на информатику»? Также было бы неплохо более конкретное название вопроса.
Шейн

Ответы:

19

Вычислимость и рекурсия, Соаре. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

Этот документ является первым из истории вычислительных работ, доступных здесь: http://www.people.cs.uchicago.edu/~soare/History/

Аарон Стерлинг
источник
1
Раздел 2.2 называется «Происхождение рекурсии».
Аарон Стерлинг
5
Интересно увидеть это математическое описание истории рекурсии. Я перепутал этот вопрос с историей концепции отречения, которая, несомненно, была основой человеческой мысли, по крайней мере, еще тогда, когда у нас была хорошая литература.
Росс Снайдер
См. Также статью Соаре в «Справочнике по теории вычислимости», 1999 г.
Каве,
Может кто-нибудь объяснить, пожалуйста, шутку с этим озадаченным не носителем языка? Согласно Google, «recusion» - это (1) неправильное написание слова «recursion» или (2) бренд-сумка Arthur & Aston. Или это как-то связано с "cusion"? Или "ругаться"?
Эмиль Йержабек поддерживает Монику
1
@ Emil, это пасхальное яйцо Google, в котором поиск рекурсии относится к самой странице поиска.
Каве
2

Из статьи о рекурсивных функциях в SEP :

Использование рекурсии восходит к 19 веку. Дедекинд [1888] использовал это понятие для получения функций, необходимых для его формального анализа концепции натурального числа. В логике рекурсия появляется в Сколеме [1923], где отмечается, что многие основные функции могут быть определены простыми приложениями метода. Современная формализация и развитие понятия происходит благодаря ряду людей, прежде всего Гёделю [1931], Хербранду, Розсе Петеру [1951] и Клини [1936]. Клини в 1952 году описал Петера как «ведущего участника специальной теории рекурсивных функций». Она представила доклад о рекурсивных функциях на Международном конгрессе математиков в Цюрихе в 1932 году.

Он предлагает следующее для получения дополнительной информации:

В частности, см. Раздел « Первые рекурсивные определения » на странице 5.

Кава
источник
1

Я не знаю, когда это появилось, но рекурсивное решение для Башен Ханоя часто используется в качестве вводного примера. Проблема возникла до формальных подходов к вычислениям.

Рафаэль
источник
2
На самом деле, нет. Ханойские башни были изобретены Эдуардом Лукасом в 1883 году, что довольно долго после первых формальных подходов к расчетам Бэббиджа и Ады Ловелас (ее статья была опубликована в 1843 году).
Джеффри Шаллит