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

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

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

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

Не первое, но важное с точки зрения практического применения: «Рекурсивные функции символьных выражений и их вычисление на машине, часть I» Джона Маккарти (в котором он представил Lisp)

Возможно, слегка касательно исходного вопроса, но запись в блоге « Как рекурсия попала в программирование: комедия ошибок » описывает интересную часть ранней истории вычислений.

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

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

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

• Род Адамс, « Ранняя история рекурсивных функций и вычислимости от Гёделя до Тьюринга », 2011.

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

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