Рекурсия что это означает что

Рекурсия

Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.

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

С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.

Содержание

В математике

В программировании

Функции

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

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

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

Данные

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

В физике

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

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

В лингвистике

В культуре

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».

Источник

Разбираемся в рекурсии

Про рекурсию ходит много шуток, и она традиционно считается одной из сложных для понимания тем в computer science, поэтому давайте сегодня немного о ней поговорим. А именно, давайте обсудим, как выражать доказуемо завершимые вычисления.

Зачем это надо? Рекурсия — один из краеугольных камней ФП, а некоторые из функциональных языков (например, Idris или Agda) обладают достаточно мощной системой типов, чтобы использовать их для проверки доказательств. А чтобы проверенным доказательствам на самом деле можно было доверять, было бы неплохо, чтобы логическая система, которую представляет система типов языка, была консистентна — то есть, если упрощать, чтобы в ней нельзя было доказать ложь.

Один из главных источников неконсистентности — незавершающиеся вычисления (для примера см. КДПВ), поэтому вышеупомянутые языки очень стараются дать возможность убедиться, что вычисления завершаются — соответствующая их часть даже имеет отдельное название, «termination checker». Но, увы, по фундаментальным причинам у любой такой проверки всегда будут ложноположительные или ложноотрицательные срабатывания, поэтому приходится идти на компромиссы. В доказательствах лучше перебдеть, чем недобдеть, поэтому всегда есть завершимые функции, которые этими языками отвергаются. Однако, эти функции можно переписать так, чтобы termination checker был доволен, если можно доказать, что рекурсивный вызов всегда в каком-то смысле «меньше».

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

Немного вводных

Сначала определим одно слово, которое дальше будет часто встречаться. Фундированное отношение на множестве — это такое отношение, у которого нет бесконечных убывающих цепочек элементов. Стандартное определение немного отличается, но для наших множеств (заведомо счётных, с другими даже идеальные Тьюринг-полные компьютеры не умеют работать) разница невелика и без аксиомы выбора. В качестве синонима в конструктивных контекстах часто используется понятие «доступности» (или как на русский перевести «accessible» в этом контексте?), которым я тоже иногда буду пользоваться.

Кроме того, немного про Агду, на которой мы и будем всё это писать. Это язык из ML-семейства с похожим на хаскель синтаксисом и с поддержкой зависимых типов. Стоит упомянуть пару синтаксических особенностей, которые не встречаются, пожалуй, ни в одном другом языке:

Ещё я иногда буду писать слово «свидетель утверждения X», обозначая этим терм, имеющий тип, соответствующий утверждению X.

Расковыриваем НОД

Один из классических примеров, на котором ломаются стандартные termination checker’ы — алгоритм Евклида для нахождения наибольшего общего делителя двух чисел. При этом он достаточно прост для того, чтобы не тратить внимание на неважные детали, да и, оказывается, в стандартной библиотеке Агды он уже реализован. Нас интересует, в частности, вот эта функция:

Здесь и дальше я буду приводить код в виде скриншотов, так как Хабр не умеет в раскрашивание Агды (что объяснимо, без запросов к тайпчекеру там не разберёшься), да и весь нужный уникод не у всех есть.

Если мы пройдём по цепочке импортов, то увидим, что Acc определён так:

Кроме того, Acc параметризован:

В принципе, можно было бы сразу подставить тело этого определения, но давайте для полноты разберёмся с типами.

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

С RecStruct всё чуть сложнее:

В любом случае, если пристально посмотреть на это определение, то станет ясно, что RecStruct принимает тип A и возвращает какой-то другой тип — функцию из Pred A в себя же, а Pred A по большому счёту является функцией A → Set — как и положено всякому благочестивому предикату в теории типов.

Но как это вообще связано с завершимостью? Почему этого Acc достаточно, чтобы доказать, что что-то завершается?

Доступность и структурная рекурсия

Оказывается, что это наша старая добрая структурная рекурсия под прикрытием.

В структурной рекурсии всё в порядке, если, сильно упрощая, мы совершаем рекурсивный вызов на синтаксическом субтерме одного из наших термов-аргументов. Вот, например, привычный Фибоначчи:

В Фибоначчи используется один из самых простых типов данных в мире, тип натуральных чисел:

но такая же логика работает и для чего-нибудь более сложного. Например, для бинарных деревьев:

Рекурсивные вызовы на каждом из поддеревьев, естественно, вполне себе корректны и доказуемо завершимы:

А теперь время для ключевого трюка. Заметим, что определение Tree выше изоморфно такому:

Аналогично можно поступить и с натуральными числами, просто в этом случае функция будет принимать аргумент типа, содержащего всего одно значение:

Подход Tree’ и ℕ’ выглядит более тяжеловесно и неуклюже, чем привычный способ описания типов, но у него есть два преимущества. Во-первых, этот подход хорошо обобщается и куда более выразителен. Например, можно представить себе дерево со счётно бесконечным числом поддеревьев в каждом узле:

Или дерево, где в каждом узле конечное, но неизвестное заранее число поддеревьев:

Во-вторых, возвращаемые значения функций, «хранящихся» в конструкторах, считаются termination checker’ом структурно меньшими, так что мы спокойно можем делать рекурсивные вызовы на этих возвращаемых значениях (и метатеория языка гарантирует, что это на самом деле всё ещё консистентно). Например, можно написать что-то в духе подсчёта глубины «диагонали» дерева с бесконечным числом детей в каждом узле:

Визуализировать эту функцию уже не так просто, как написать, но написать можно, и termination checker вполне корректно будет считать её тотальной.

Если вернуться к нашим НОДам, то можно заметить, что Acc имеет примерно ту же форму, что и все эти забавные типы, описанные выше. В частности, конструктор Acc _ принимает функцию, которая по элементу y и свидетелю y возвращает другой Acc (конкретнее, значение типа Acc _ ). Теперь мы знаем, что termination checker считает этот Acc _ как структурно меньший, чем исходный Acc _ (кстати, даже несмотря на то, что его тип отличается). Поэтому мы можем передать это новое значение в рекурсивный вызов, и termination checker с удовольствием посчитает это корректной завершимой рекурсией, даже если ни один из прочих аргументов не стал структурно меньше.

В каком-то смысле Acc позволяет преобразовать «меньше-согласно-отношению» в «структурно-меньше», и нам, программистам, остаётся заполнить пробелы в этом преобразовании.

Примеры

Но как именно выглядит это преобразование?

Натуральные числа

Это доказательство — просто объект типа Acc _ для любого x :

После обычных для Агды пасов мы придём к чему-то вроде такого:

Если теперь перейти ко второй дырке, убрать dot pattern и дать имя первому аргументу, то получим что-то такое:

В дырке при этом будет такая цель и такой контекст:

Пары чисел

Что насчёт чего-нибудь более сложного, как, например, пар натуральных чисел с лексикографическим порядком?

Такой порядок можно определить, например, так:

Доказательство его фундированности предлагается читателю в качестве упражнения.

Ладно, шучу, мне просто лень описывать процесс разработки доказательства. Конечный результат будет выглядеть примерно так:

Контрпримеры

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

Тривиальный тип

Пожалуй, самый простой пример — тип-синглтон с отношением, которое выполняется для любых двух элементов этого типа (тривиальным образом, так как у этого типа всего один элемент):

Давайте начнём писать доказательство фундированности:

Каков тип этой дырки?

Единственный способ создать значение типа Acc — через конструктор acc :

Какой тип дырки перед нами после этого?

Ходим кругами

Что насчёт чего-нибудь поинтереснее? Давайте поиграем в камень-ножницы-бумагу, также известные как числа Пеано без аксиомы ∀x. suc(x) ≠ 0 на трёхэлементном множестве:

Из-за конечности Obj представляется разумным попытаться доказать фундированность через case split по аргументу. Затем давайте рассмотрим произвольную ветку после сплита (я люблю метал, поэтому выберу rock ):

Бесконечные цепи уникальных элементов

Или, другими словами, пусть у нас есть такой свидетель. Тогда мы можем скормить ему 0, заем 1, затем 2, и так далее. Так как мы по факту имеем структурную рекурсию, то мы сможем написать незавершающееся вычисление, но, так как Агда консистентна, этого не может быть!

Или, в виде кода, кратко и ясно:

Наконец-то рекурсия

Как же используется доказательство фундированности? Посмотрим ещё раз на функцию вычисления НОД:

Заключение

После этого маленького экскурса у меня получилось написать что-то чуть менее тривиальное, с кучей взаимно рекурсивных функций, бегающих по взаимно рекурсивным деревьям вывода в системе типов, формализацией которой я сейчас занимаюсь. Надеюсь, что если тебе, дорогой читатель, понадобится доказуемо завершимая рекурсия, эти записи помогут тебе с ней разобраться. Тем более, что, на мой взгляд, чаще всего все доказательства завершимости сводятся к введению размера как прямого отображения на множество натуральных чисел, а там с фундированностью всё просто, и 640 килобайт Acc _ хватит всем.

Источник

Рекурсия. Беглый взгляд

Ниже речь пойдёт о старушке рекурсии, которую неплохо бы представлять, понимать и применять.

Примечание: Данная небольшая статья написана для беглого ознакомления с рекурсией, некоторыми примерами её применения и опасностями.

Определение

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

Самая большая глупость — это делать то же самое и надеяться на другой результат.

Под рекурсией понимают процесс повторения элементов самоподобным образом. Объект обладает рекурсией, если он является частью самого себя.

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

Некоторые примеры

Рекурсию надо бы понять, а определение для этого подходит хуже, чем наглядные примеры. Для лучшего понимания, конечно, всё же следует прочитать определение, посмотреть на пример, снова прочитать определение и снова посмотреть на пример… Повторять, пока не придёт осознание.

Отличный пример вы можете найти тут.

Самое известное программисту применение рекурсии — задачи на вычисление чисел Фибоначчи или факториала. Давайте покажем, как это реализовать на языке C:

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

Fork-бомба
Примечание: Рекурсивное создание процессов крайне быстро (из-за экспоненциального роста их количества) заполняет таблицу процессов, что достаточно опасно для системы.

Reboot кнопкой после такого делать немного не приятно.

Для математика первой ассоциацией, скорее всего, будет фрактал. Фракталы прекрасны и приятно для глаза показывают свойства самоподобия.

Самые известные фракталы:

Ну и в повседневной жизни классическим примером являются два зеркала, поставленных друг напротив друга.

Углубимся глубже

Проста ли рекурсия? Однозначно нет. На вид кажется, что всё просто, однако рекурсия таит в себе опасности (А иногда она просто не понятна).

Вернёмся к примеру с вычислением чисел Фибоначчи. Сразу заметим, что возвращаемым результатом функции является вызов этой же функции, а если быть точнее, то сумма результатов вызова двух функций (именно поэтому рекурсия не хвостовая). Становится понятно, что второй вызов не произойдёт, пока не завершится первый (в котором также будет вызов двух функций). Тут же пытливый ум заметит, что из рекурсивной функции должен существовать «нормальный» выход, без самовызова, иначе мы познакомимся с переполнением стека вызовов — это один из ключевых моментов, который стоит держать в голове при работе с функциями вызывающими сами себя.

Заметим, что дерево вызовов получится большим, но максимальное количество вызовов в стеке будет заметно меньше (N-1 при N > 2, соответственно).

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

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

Для полноты картины обязательно надо упомянуть о борьбе с рекурсией.

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

Под силу ли побороть любую рекурсию?

Однозначно да. Любой рекурсивный алгоритм можно переписать без использования рекурсии, а хвостовую рекурсию же очень легко перевести на итерацию (чем и занимаются некоторые компиляторы для оптимизации). Это также относится и к итерационным алгоритмам.

Самый известный способ — это использование стека. Здесь подробнее, для интересующихся.

Заключение

Спасибо за прочтение статьи. Надеюсь, что большинство не знакомых с рекурсией получили базовое представление о ней, а от знающих людей, конечно, хочется услышать дополнения и замечания в комментариях. Не бойтесь рекурсии и не переполняйте стек!

UPD: Добавлен корректный пример хвостовой рекурсии.

Источник

Рекурсия

Рекурсия — это жемчужина теории алгоритмов, и это первое, с чем знакомят школьников (сразу после процедур ввода и вывода данных, элементарных арифметических операций, оператора цикла и условного оператора).

Простота рекурсии обманчива. Метод рекурсии таит в себе много опасностей и сложностей, и в то же время готовит много приятных сюрпризов.

Давно известен такой математический приём, как разбиение задачи на простые шаги, каждый из которых тоже можно разложить на более мелкие шаги и так далее, пока не доберёмся до самых элементарных «шажочков».

Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример слишком прост. Далее мы рассмотрим более сложные примеры, освещающие явление рекурсии как с хорошей так, и с плохой стороны.

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

Содержание

Числа Фибоначчи [ править ]

Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.

Проблемы рекурсии и как их решать [ править ]

Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память.

Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:

Такая рекурсия с запоминанием называется динамическим программированием сверху.

Рекурсию с запоминанием для вычисления чисел Фибоначчи мы привели просто для демонстрации идеи. Для чисел Фибоначчи есть простой «человеческий алгоритм», не использующий рекурсивные вызовы и запоминание всех вычисленных значений. Достаточно помнить два последних числа Фибоначчи, чтобы вычислить следующее. Затем предпредыдущее можно «забыть» и перейти к вычислению следующего:

F ( n ) = 1 5 ( ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ) <\displaystyle F(n)=<\frac <1><\sqrt <5>>>\left(\left(<\frac <1+<\sqrt <5>>><2>>\right)^-\left(<\frac <1-<\sqrt <5>>><2>>\right)^\right)> .

Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке Mathematica (см. http://www.wolfram.com):

Простое рекурсивное определение: F(n_) := F(n-1) + F(n-2); F(1) = F(2) = 1;

Рекурсивное определение с запоминанием: F[n_] := (F[n] = F[n-1] + F[n-2]); F[1] = F[2] = 1;

Задача 1 [ править ]

Задача 2 [ править ]

Задача 3 [ править ]

Задача 4 [ править ]

Задача о золотой горе [ править ]

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

Формулировка задачи: На рисунке показан пример треугольника из чисел. Написать программу, вычисляющую наибольшую сумму чисел, через которые проходит путь, начинающийся на вершине и заканчивающийся где-то на основании.

В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.

В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.

Пример входных данных:

Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.

На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.

Задача 5 [ править ]

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

Задача «Сделай палиндром» [ править ]

Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например «АБА» или «АББ ББА». Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?

Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.

Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998 году. Рассмотрим её решение, основанное на рекурсии.

Алгоритм Евклида [ править ]

Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется наибольший общий делитель (НОД) (GCD — Greatest Common Divisor).

Пример: Вход: 18, 600 Выход: 6

Рассмотрим второе свойство. При замене одного из чисел на его разность с первым, наибольший общий делитель остаётся прежним.

3 5 = 1 1 + 1 1 + 1 2 <\displaystyle <\frac <3><5>>=<\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><2>>>>>>> , 5 8 = 1 1 + 1 1 + 1 1 + 1 2 <\displaystyle <\frac <5><8>>=<\frac <1><\displaystyle 1+<\displaystyle <\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><2>>>>>>>>>> , 8 13 = 1 1 + 1 1 + 1 1 + 1 1 + 1 2 <\displaystyle <\frac <8><13>>=<\frac <1><\displaystyle 1+<\displaystyle <\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><2>>>>>>>>>>>> .

Задача 6 [ править ]

Задача 7 [ править ]

При построении рекурсивной функции важно ответить на следующие вопросы:

Одно из важных достоинств рекурсивных алгоритмов заключается в том, что они просты и наглядны. Но рекурсия не всегда является эффективным (самым быстрым) решением. Рекурсия использует мало памяти, но работать может довольно долго, как в примере с числами Фибоначчи.

Задача 8 [ править ]

Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:

Задачи для самостоятельного решения [ править ]

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

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

Задача 9 [ править ]

Задача 10 [ править ]

Задача 11 [ править ]

Эта строчка содержит рекурсивное определение объекта s : «объект типа s может быть получен из объекта типа s с помощью окружения его открывающейся и закрывающейся круглой скобки, или с помощью приписывания двух объектов типа s друг к другу, либо это просто пустое слово». Вертикальная черта в нотации EBNF означает союз «или». С помощью одинарных кавычек выделяют символы или строки символов, пробелы играют роль разделителей.

Задача 12 [ править ]

Задача 13 [ править ]

Задача коммивояжёра [ править ]

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

Коммивояжёр (франц. commis voyageur), разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и тому подобное.

Наш коммивояжёр ездит по городам с целью сбыта товаров разного рода. Он всегда начинает и заканчивает свой путь в одном и том же городе. На проживание во всех городах коммерсант тратит одинаковую сумму денег. Поэтому существенна только сумма на проезд из города в город. Есть список городов и стоимость проезда между некоторыми парами городов.

Задача коммивояжёра — побывать во всех городах (не менее одного раза) и при этом потратить как можно меньше денег на проезд и вернуться обратно.

Стоимости проезда между парами городов записаны в следующем формате:

Результат записывается в следующем формате:

Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.

Снежинка Коха [ править ]

Снежинка Коха — это фрактальное множество точек на плоскости, которое похоже на снежинку.

Здесь приведена программа на языке PostScript. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.

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

Программа «Снежинка Коха»

Заключение [ править ]

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

Источник