Рекурсия

Бесконечное отражение как пример рекурсии : человек сидит с зеркалом перед большим настенным зеркалом. Следующее за этим зеркальное отображение содержит себя как часть.

Поскольку рекурсия ( лат. Recurrere 'бег назад' ) - это принцип бесконечного процесса, который сам содержится как часть или с помощью самоопределяемого имени. Обычно рекурсивные процессы могут быть описаны относительно кратко или могут быть запущены относительно короткой инструкцией. Частичные процессы или объекты, созданные один за другим, не являются независимыми друг от друга в случае рекурсии, но между каждой парой шагов или парой объектов существует особая рекурсивная связь.

«Термин [рекурсия] очень широк». В природе это часто наблюдаемый процесс (например, во время роста растений ). Его воссоздают во многих сферах культуры , например, в изобразительном искусстве , где феномен именуемый mise en abyme . Рекурсия - это общий термин в математике и информатике .

Рекурсия также является стратегией решения проблем. Сложные проблемы часто можно очень элегантно уловить с помощью рекурсивно сформулированных правил. Основной принцип состоит в том, чтобы свести общую задачу к более простой задаче того же класса. Это будет включать Также используется в так называемом рекурсивном программировании : чтобы создать рекурсию, процедура , функция или метод должны только вызвать себя . Этот процесс продолжается до тех пор, пока не вступит в силу условие прерывания, содержащееся в программе.

В математике рекурсивная формулировка используется для объяснения функций (см. Рекурсивное определение ).

Вводные примеры рекурсии

Рекурсивная графика

«Прорастание» дерева Пифагора

Рекурсивные правила также могут быть использованы при создании графики, в результате получаются так называемые фракталы - эстетически приятные, естественно выглядящие структуры. Одним из примеров является дерево Пифагора . Возникает по следующему правилу (третий шаг показывает рекурсию):

  • Постройте квадрат на заданной базовой линии .
  • Нарисуйте треугольник с заданными углами и высотой на его верхней стороне .
  • Снова примените два вышеуказанных шага к двум свободным сторонам только что созданного треугольника.

Затем этот алгоритм разворачивается до указанной глубины рекурсии : если он выполняется один раз, создается треугольник с квадратами на каждой из трех сторон. Это похоже на иллюстрацию теоремы Пифагора - отсюда и название. Чем больше глубина рекурсии, тем больше структура напоминает дерево.

Вы можете пропустить первые два шага в описании выше и начать рекурсивный процесс с иллюстрации теоремы Пифагора:

  • Используйте эту иллюстрацию, чтобы создать еще две похожие иллюстрации, каждая из которых имеет большой квадрат, идентичный одному из двух маленьких квадратов на предыдущей иллюстрации.
  • Используя ту же процедуру, создайте еще две похожие иллюстрации и т. Д. Из каждой из иллюстраций, созданных на первом этапе.

Рекурсия в грамматике

Грамматика естественных языков используется в лингвистике, среди прочего. описывается с помощью так называемых правил структуры фраз . Большинство лингвистов считают, что все человеческие языки обладают свойством быть рекурсивным (в отличие от сигнальных систем в царстве животных). Это происходит потому, что при декомпозиции грамматической единицы, помеченной категорией, та же самая категория может появиться снова. Примером может служить феномен придаточных предложений , который описывается здесь следующим упрощенным правилом производства:

  1. S → NP VP (предложение состоит из существительной (как подлежащее) и глагольной фразы )
  2. VP → V NP * (глагольная фраза состоит из глагола и от нуля до многих именных фраз как объектов глагола)
  3. VP → VS (глагольная фраза состоит из глагола и придаточного предложения как объект глагола)

Эта грамматика позволяет вам выбирать, писать ли «VP» по правилу 2 или 3. Если вызываются шаги 1 и 3, возникает рекурсия: символ S появляется как продукт правила 3, которое, в свою очередь, представляет начало правила 1.

Рекурсия по математике

Рекурсия играет важную роль в математике, например, в рекурсивном определении функций. Вычисление факториала и последовательности Фибоначчи показаны ниже в качестве примеров . Однако в математике методы рекурсии и рекурсивные определения не ограничиваются функциями натуральных чисел.

Факультет

Функциональный факториал натурального числа определяется как произведение чисел 1 на :

Примеры

Если этот список будет продолжен, рекурсивность будет почти автоматически получена при вычислении 5! вы не начнете с самого начала, но можете вернуться к предыдущим результатам, поэтому

В общем, функцию можно определить рекурсивно :

Последовательность Фибоначчи

Классическим примером рекурсивной функции является последовательность Фибоначчи , в которой каждый дополнительный член в последовательности является суммой двух предыдущих:

В отличие от факториальной функции здесь нет тривиального замкнутого представления. Самое простое описание - это рекурсивное определение:

Это рекурсивное определение каскадно. Используя это определение, третье число Фибоначчи рассчитывается следующим образом:

Расчет здесь проводится несколько раз. Это указывает на то, что есть потенциал для оптимизации.

Формальные типы рекурсии

Наиболее распространенной формой рекурсии является линейная рекурсия , при которой в каждом случае рекурсивного определения может произойти не более одного рекурсивного вызова. Затем расчет выполняется по цепочке вызовов. При такой рекурсии дерево вызовов не содержит ветвей.

Примитивная рекурсия является частным случаем линейной рекурсии, которая всегда с помощью итерации может быть заменена (смотрите ниже соотношения рекурсии # для итерации и ). Здесь функции определены на натуральных числах, причем первый параметр увеличивается или уменьшается на единицу в каждом рекурсивном вызове. Каждое примитивно-рекурсивное определение может быть заменено циклом (например, For Loop или While Loop ) с помощью стека .

Терминал или повторяющиеся рекурсии ( хвост рекурсии или в конце рекурсии ) описывает частный случай линейной рекурсии, в которой каждый рекурсивный вызов является последним действием рекурсивного вызова. Конечные рекурсии можно заменить циклами while и наоборот. (В отличие от конечной рекурсии - это головная рекурсия ; см. Раздел Бесконечная регрессия ).

Под вложенной рекурсией понимается рекурсия, которая возникает при рекурсивных вызовах в выражениях параметров рекурсивных вызовов. Эту форму рекурсии чрезвычайно сложно понять.

Каскадная рекурсия описывает случай, когда несколько рекурсивных вызовов находятся рядом друг с другом. Затем рекурсивные вызовы образуют дерево. Каскадная рекурсия считается элегантной, но без дополнительных мер она может привести к экспоненциальным вычислениям. Его часто используют в качестве отправной точки для получения другой, более эффективной формулы.

Взаимная рекурсия называет определение нескольких функций взаимного использованием друг с другом. Его можно проследить до обычной рекурсии кортежнозначной функции.

Рекурсия в программировании

Более высокие языки программирования, которые работают с функциями, обычно также допускают рекурсию. В большинстве случаев решения можно указывать рекурсивно или итеративно.

О связи между рекурсией и итерацией

Рекурсия и итерация - по сути, одинаково эффективные подходы. Одинаковые или похожие процессы повторяются несколько раз, разница заключается в используемом алгоритме .

В случае итерации команда, состоящая из нескольких частей, должна выполняться через несколько циклов ( for, while ...) до тех пор, пока не будет выполнено условие прерывания. В случае рекурсии достаточно просто добавить процедуры или функции с запросом на их повторное использование с регулярно изменяемым параметром до тех пор, пока не будет выполнено условие завершения.

Рекурсия обычно обходится меньшим количеством исходного кода и более понятна (для опытных пользователей) - в этом случае не нужно определять вспомогательные переменные и счетчики циклов. С точки зрения обработки итерационные процессы обычно более эффективны и требуют меньше места для хранения. Причина в том, что повторяющиеся вызовы функций помещаются в стек со всеми временно сохраненными значениями . В частности, рекурсия также может включать причину переполнения буфера (StackOverflow). Поэтому при программировании систем реального времени на микроконтроллерах часто избегают рекурсии.

Некоторые языки программирования (например, в функциональном программировании ) не допускают итерацию, поэтому всегда необходимо выбирать рекурсивную реализацию. Такие языки часто используют примитивные рекурсии для оптимизации, которые внутренне реализуются как итерации (некоторые интерпретаторы для LISP и Scheme действуют, как указано выше).

Следует отметить, что наивная реализация некоторых функций (например, чисел Фибоначчи ) требует, чтобы частные решения вычислялись несколько раз. В этом примере исправление обеспечивается запоминанием , которое основано на повторном использовании промежуточных решений, которые уже были рассчитаны. Рекурсия является неотъемлемой частью некоторых конструктивных стратегий для эффективных алгоритмов , особенно разделяй и властвуй стратегия (разделяй и властвуй) . Другие подходы (например, так называемые жадные алгоритмы ) требуют итеративного подхода. Рекурсия и примитивно рекурсивные функции играют важную роль в теоретической информатике , особенно в теории сложности и теории вычислимости (см также лямбда - исчисление и функция Аккермана ).

В компиляторе, который является рекурсивным спуском (Recursive Descent), используется метод, в котором язык рекурсивно анализируется .

Примеры программирования

В следующем примере показана простая и популярная реализация функции факториала на языке программирования Python . Для ясности рекурсивный вариант противопоставляется итеративному варианту. Рекурсия выражается в том, что функция вызывает себя с аргументом, уменьшенным на 1. Обе реализации выполняют алгоритм с линейной сложностью выполнения в зависимости от входного параметра. В то время как сложность пространства остается постоянной в итеративном варианте, потребность в памяти увеличивается линейно в рекурсивном варианте, поскольку новая область памяти должна быть зарезервирована для локальных переменных и адреса возврата при каждом вызове рекурсивной функции. В функциональном программировании управление динамической памятью реализуется с помощью стека вызовов .

Итеративное программирование Рекурсивное программирование
def factorial(number):
    result = 1
    
    while number > 1:
        result *= number
        number -= 1
    
    return result
def factorial(number):
    if number <= 1:
        return 1
    
    return number * factorial(number - 1)

Следующий пример реализует последовательность Фибоначчи в C программирования языка . Рекурсивный вариант - это множественная рекурсия, которая приводит к экспоненциальному увеличению времени выполнения и пространственной сложности. Рекурсивные вызовы функций переходят в двоичное дерево, в котором идентичные частичные результаты вычисляются несколько раз. Чаще всего числа Фибоначчи вычисляются в первых двух местах, которые определяют условие завершения рекурсии. В итеративном варианте сложность выполнения линейна, а сложность пространства постоянна.

Итеративное программирование Рекурсивное программирование
int fibonacci(int number) {
    int first = 0, second = 1;

    for (int count = 0; count < number; ++count) {
        int summand = first;
        first = second;
        second += summand;
    }

    return first;
}
int fibonacci(int number) {
    if (number <= 0)
        return 0;

    if (number == 1)
        return 1;

    return fibonacci(number - 1) + fibonacci(number - 2);
}

Разрешение рекурсий

При решении рекурсии, с одной стороны, учитываются затраты времени выполнения, а с другой - явная форма рекурсии.

Усилия могут быть определены как асимптотические- или-границы с использованием основной теоремы или метода подстановки . Даже умные ставки с последующей индукцией обеспечивает способ верхней границы для определения длительности.

Явный вид (также называется замкнутой формы) уравнения рекурсии можно найти, например, с помощью порождающей функции. Вторая возможность - это получение последовательных значений функции повторения путем формирования разности.

Различные способы использования рекурсии в разных и более широких науках

Понятие рекурсии по-разному используется в разных дисциплинах. Можно выделить пять типов использования: «организационно-синтаксическая» рекурсия в когнитивной психологии, «операционально-функциональная» рекурсия в теории технологий и «эмулятивная рекурсия процесса» в культурной эволюции и теории цивилизации.

Когнитивная психология

Эволюционный когнитивный психолог Майкл Корбаллис разработал «организационно-синтаксическую» концепцию рекурсии в своей книге «Рекурсивный разум» . Это показывает, что человеческая способность к вложенным уровням значения и действия на любой глубине и к открытому синтаксическому связыванию операционных единиц, как они в основном проявляются в поведении и сотрудничестве инструментов, предшествует языковой способности и является общей характеристикой человеческого познания и организации действий . Сильная человеческая способность к мысленным путешествиям во времени и теория разума основана на способности к рекурсии.

Инженерная теория

Системный теоретик У. Брайан Артур разработал «операционально-функциональную» концепцию рекурсии в своей книге «Природа технологии» . Артур показывает, что все технологии имеют иерархическую вложенность элементов и функциональных уровней, при этом нижние элементы получают свои функциональные возможности через рекурсию на верхние уровни, как показано на примере ассоциации авианосцев: турбина истребителя состоит из отдельных элементов. части или «исполняемые файлы», такие как винты и воздушные лопасти, которые рекурсивно встроены в общую функцию турбины, поскольку в то же время турбина является рекурсивно вложенным «исполняемым файлом» реактивного истребителя, реактивный истребитель является «исполняемым файлом "авианосного объединения, а это" исполняемый "эскадрильи.

Исследования культурной эволюции и теория цивилизации

Как показал социолог Приор Лёффлер, все технологическое и культурное развитие в культурной эволюции и истории цивилизации имеет модель «прозессемулятивной» рекурсии. «Эмуляционная» рекурсия описывает механизм разработки, в котором инструментальный или интеллектуальный процесс абстрагируется и повторно вводится как эмуляция материала или носителя. Это можно продемонстрировать на раннем этапе технологической эволюции, на которой каждую стадию развития можно описать как степень рекурсии. В соответствии с текущим уровнем знаний, обобщенным в «модели расширения культурных возможностей», простые каменные орудия («модульная культура»,> 2,6 млн. Лет ) следуют с точки зрения развития композитных инструментов, таких как молотковые камни с ручками или копья с костяными наконечниками («композитная культура »,> 500 тыс. лет назад ), затем состоящие из дополнительных независимых модулей, таких как лук и стрела или игла и нить («дополнительная культура»,> 70 тыс. лет назад ), а затем идеальные инструменты, такие как наскальные рисунки, музыкальные инструменты или ловушки («идеальная культура»,> 40 тыс. лет ). Технологические структуры кумулятивных стадий развития основаны на «процессно-эмуляционной» рекурсии процессов предыдущих стадий. Например, устройство лука и стрел («дополнительная культура») рекурсивно имитирует процесс метания копья («составная культура»), а ловушка («идеальная культура») рекурсивно имитирует присутствие группы охотников или механизм ловушки имитирует спусковой механизм лука («Дополнительная культура»). Как общий принцип, «эмуляционная» рекурсия проходит через всю историю развития технологии: например, микроволновая печь основана на «эмуляционной» рекурсии, поскольку она имитирует процесс нагрева пищи, например, в духовке; Распознавание цифровых образов основано на процессной эмуляционной рекурсии распознавания человеческих образов и т. Д. Было показано, что принцип развития «процессной эмуляционной» рекурсии также лежит в основе развития всей истории цивилизации и происходит в дополнение к технологиям. в других областях, таких как экономика, средства массовой информации, политика, развитие когнитивных структур, искусство и математика, причем каждый этап развития в этих областях основан на рекурсивной имитации процессов предыдущего этапа развития. Таким образом, кумулятивные последовательные фазы развития в истории цивилизации ( ранние развитые цивилизации , осевое и современное время ) могут быть объяснены как выражения рекурсий «эмуляции процесса».

Смотри тоже

веб ссылки

Викисловарь: рекурсия  - объяснение значений, происхождение слов, синонимы, переводы
Викисловарь: рекурсивный  - объяснение значений, происхождение слов, синонимы, переводы

литература

Никлаус Вирт: алгоритмы и структуры данных . 5-е издание. Б. Г. Тойбнер, Штутгарт, 2000 г. (1-е издание: 1975 г.). ISBN 978-3-519-22250-7 , DOI: 10.1007 / 978-3-322-80154-8 .

Замечания

Индивидуальные доказательства

  1. Никлаус Вирт , стр. 149: 3. Рекурсия, 3.1. вступление
  2. Никлаус Вирт : Algorithmen und Datenstruktur , BG Teubner 1983, стр. 150: «Суть рекурсии - это возможность определения бесконечного числа объектов с помощью конечного оператора».
  3. a b Bussmann, Hadumod, ed. (1990): Lexikon der Sprachwissenschaft. Alfred-Kröner-Verlag, Stuttgart, p. 640: Рекурсия - это термин в лингвистике, «который описывает формальное свойство грамматик генерировать бесконечное количество предложений с конечным набором элементов и конечным набором правил». (Помимо примеров из языка, природы, искусства и поэзии, цитирует математику и программирование, например, в uni-leipzig: Recursion in language ).
  4. Дуглас Р. Хофштадтер : Гёдель, Эшер, Бах , dtv , 2004, стр.137
  5. См., Например, Б. Эндрю Карни: Конституционная структура. Второе издание. Oxford University Press, 2010. По вопросу о рекурсивности v. а. С. 84 и далее.
  6. Только для языка Pirahã был выдвинут тезис о том, что он не знает рекурсии в грамматике, поскольку здесь нет придаточных предложений. Этот анализ противоречивый, подробности см. В связанной статье.
  7. По поводу этих пяти типов см. Давор Лёффлер: Генеративные реальности I. Технологическая цивилизация как новая осевая эпоха и уровень цивилизации. Антропология 21 века . Weilerswist: Velbrück Wissenschaft, 2019, стр. 195–204.
  8. См. Давор Лёффлер: Генеративные реальности I. Технологическая цивилизация как новая осевая эпоха и уровень цивилизации. Антропология 21 века . Weilerswist: Velbrück Wissenschaft, 2019, стр. 197 f.
  9. Майкл С. Корбаллис, Рекурсивный разум. Истоки человеческого языка, мысли и цивилизации . Принстон, Нью-Джерси / Оксфорд: Princeton University Press, 2013.
  10. См. Майкл С. Корбаллис: Рекурсивный разум. Истоки человеческого языка, мысли и цивилизации . Принстон, Нью-Джерси / Оксфорд: Princeton University Press, 2013, стр. 82-165.
  11. См. Давор Лёффлер: Генеративные реальности I. Технологическая цивилизация как новая осевая эпоха и уровень цивилизации. Антропология 21 века . Weilerswist: Velbrück Wissenschaft, 2019, стр. 198 f.
  12. ^ В. Брайан Артур: Природа технологии. Что это такое и как развивается . Лондон: Penguin Books, 2009.
  13. См. У. Брайан Артур: Природа технологии. Что это такое и как развивается . Лондон: Penguin Books, 2009, стр.29.
  14. См. У. Брайан Артур: Природа технологии. Что это такое и как развивается . Лондон: Penguin Books, 2009, стр. 39-44.
  15. См. Давор Лёффлер: Генеративные реальности I. Технологическая цивилизация как новая осевая эпоха и уровень цивилизации. Антропология 21 века . Weilerswist: Velbrück Wissenschaft, 2019, стр. 199–204.
  16. Мириам Н. Хайдл, Майкл Болус, Марк Коллард и др.: Природа культуры: восьмиуровневая модель эволюции и расширения культурных возможностей гомининов и других животных . В: Журнал антропологических наук , том 93, 2015 г., стр. 43–70.
  17. См. Мириам Н. Хайдл, Майкл Болус, Марк Коллард и др.: Природа культуры: восьмиуровневая модель эволюции и расширения культурных возможностей гомининов и других животных . В: Журнал антропологических наук , том 93, 2015 г., стр. 56 f.
  18. См. Мириам Н. Хайдл, Майкл Болус, Марк Коллард и др.: Природа культуры: восьмиуровневая модель эволюции и расширения культурных возможностей гомининов и других животных . В: Журнал антропологических наук , том 93, 2015 г., стр. 57 f.
  19. Мириам Н. Хайдл, Майкл Болус, Марк Коллард и др.: Природа культуры: восьмиуровневая модель эволюции и расширения культурных возможностей гомининов и других животных . В: Журнал антропологических наук , том 93, 2015 г., с. 58.
  20. Мириам Н. Хайдл, Майкл Болус, Марк Коллард и др.: Природа культуры: восьмиуровневая модель эволюции и расширения культурных возможностей гомининов и других животных . В: Журнал антропологических наук , том 93, 2015 г., стр. 58-60.
  21. Сводную таблицу можно найти в книге Давора Лёффлера: Генеративные реальности I. Технологическая цивилизация как новая осевая эпоха и этап цивилизации. Антропология 21 века . Weilerswist: Velbrück Wissenschaft, 2019, стр. 600 f.
  22. См. Давор Лёффлер: Генеративные реальности I. Технологическая цивилизация как новая осевая эпоха и уровень цивилизации. Антропология 21 века . Weilerswist: Velbrück Wissenschaft, 2019, стр. 621–640.