Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Программирование рекурсивных алгоритмов

Рекурсия в программировании. Анализ алгоритмов

Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:

  • структуры данных:
    • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
    • строка состоит из первого символа и подстроки (меньшей строки);
  • шаблоны проектирования, например декоратор[1]. Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. Детально рекурсивные шаблоны изучил Мак-Колм Смит, выделив в своей книге общий шаблон проектирования — Recursion [2];
  • рекурсивные функции (алгоритмы) выполняют вызов самих себя.

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

Содержание:

Примеры рекурсивных алгоритмов

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

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

Поиск элемента массива

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

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

Двоичный поиск в массиве

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

Вычисление чисел Фибоначчи

Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: (F_0 = 0, F_1 = 1, F_n = F_ + F_, n > 2).

Быстрая сортировка (quick sort)

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

Блок-схема алгоритма быстрой сортировки

Сортировка слиянием (merge sort)

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

Блок схема сортировки слиянием

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

Анализ рекурсивных алгоритмов

При анализе сложности циклических алгоритмов рассчитывается трудоемкость итераций и их количество в наихудшем, наилучшем и среднем случаях [4]. Однако не получится применить такой подход к рекурсивной функции, т.к. в результате будет получено рекуррентное соотношение. Например, для функции поиска элемента в массиве:

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

Метод подстановки (итераций)

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

Можно предположить, что (T^_n = T^_ + ktimesmathcal(1)), но тогда (T^_n = T^_ <0>+ ntimesmathcal(1) = mathcal(n)).

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

Метод математической индукции

Позволяет доказать истинность некоторого утверждения ((P_n)), состоит из двух шагов:

  1. доказательство утверждения для одного или нескольких частных случаев (P_0, P_1, …);
  2. из истинности (P_n) (индуктивная гипотеза) и частных случаев выводится доказательство (P_).

Докажем корректность предположения, сделанного при оценки трудоемкости функции поиска ((T^_n = (n+1)timesmathcal(1))):

  1. (T^_ <1>= 2timesmathcal(1)) верно из условия (можно подставить в исходную рекуррентную формулу);
  2. допустим истинность (T^_n = (n+1)timesmathcal(1));
  3. требуется доказать, что (T^_ = ((n+1)+1)timesmathcal(1) = (n+2)timesmathcal(1));
    1. подставим (n+1) в рекуррентное соотношение: (T^_ = mathcal(1) + T^_n);
    2. в правой части выражения возможно произвести замену на основании индуктивной гипотезы: (T^_ = mathcal(1) + (n+1)timesmathcal(1) = (n+2)timesmathcal(1));
    3. утверждение доказано.

Часто, такое доказательство — достаточно трудоемкий процесс, но еще сложнее выявить закономерность используя метод подстановки. В связи с этим применяется, так называемый, общий метод [5].

Общий (основной) метод решения рекуррентных соотношений

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

(T_n = acdot T(frac)+f_n; a, b = const, a geq 1, b > 1, f_n > 0, forall n).

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

  1. (exists varepsilon > 0 : f_n = mathcal(n^) Rightarrow T_n = Theta(n^));
  2. (f_n = Theta(n^) Rightarrow T_n = Theta(n^ cdot log n));
  3. (exists varepsilon > 0, c 1).

Для проведения анализа может использоваться метод подстановки или следующие рассуждения: каждый рекурсивный вызов уменьшает размерность входных данных на единицу, значит всего их будет n штук, каждый из которых имеет сложность ( mathcal(1)). Тогда (T^_n = n cdot mathcal(1) = mathcal(n)).

Анализ алгоритма сортировки слиянием

Исходные данные разделяются на две части, обе из которых обрабатываются: (a = 2, b = 2, n^ = n).

При обработке списка, разделение может потребовать выполнения (Theta(n)) операций, а для массива — выполняется за постоянное время ((Theta(1))). Однако, на соединение результатов в любом случае будет затрачено (Theta(n)), поэтому (f_n = n).

Используется второй случай теоремы: (T^_n = Theta(n^ cdot log n) = Theta(n cdot log n)).

Анализ трудоемкости быстрой сортировки

В лучшем случае исходный массив разделяется на две части, каждая из которых содержит половину исходных данных. Разделение потребует выполнения n операций. Трудоемкость компоновки результата зависит от используемых структур данных — для массива (mathcal(n)), для связного списка (mathcal(1)). (a = 2, b = 2, f_n = b), значит сложность алгоритма будет такой же как у сортировки слиянием: (T^_n = mathcal(n cdot log n)).

Однако, в худшем случае в качестве опорного будет постоянно выбираться минимальный или максимальный элемент массива. Тогда (b = 1), а значит, мы опять не можем использовать основную теорему. Однако, мы знаем, что в этом случае будет выполнено n рекурсивных вызовов, каждый из которых выполняет разделение массива на части ((mathcal(n))) — значит сложность алгоритма (T^_n = mathcal(n^2)).

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

Хвостовая рекурсия и цикл

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

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

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

В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше алгоритмы поиска и бинарного поиска [4]. В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой — компиляторы автоматически заменяют ее циклом.

Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра [7], который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала:
(fact_n = n cdot fact(n-1) \
fact_3 = 3 cdot fact_2 = 3 cdot (2 cdot fact_1) = 3cdot (2 cdot (1 cdot fact_0)) = 6 \
fact_n = factTail_ \
\
factTail_ = factTail(n-1, accumulator cdot n)\
factTail_ <3, 1>= factTail_ <2, 3>= factTail_ <1, 6>= factTail_ <0, 6>= 6
)

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

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

Программирование рекурсивных алгоритмов

Понятие рекурсии

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

Широкое проникновение рекурсивных методов в практику программиро­вания началось с распространения универсального языка программирования АЛГОЛ-60, допускающего рекурсивное обращение к процедурам. Рекурсия отражает существенную характерную черту абстрактного мышления, проявляющуюся при анализе сложных алгоритмических и структурных конструкций в самых различных приложениях. Пользуясь рекурсией, мы избавляемся от необходимости утомительного последовательного описания конструкции и ограничиваемся выявлением взаимосвязей между различными уровнями этой конструкции.

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

Программирование с использованием рекурсии

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

Function Factorial (N: Integer): Integer;

if N = 1 Then Factorial := 1

Else Factorial := N*Factorial(N -1)

Здесь Factorial(N) определяется через значение Factorial(N-1), которое определяется через Factorial(N-2), и т.д. до сведения к значению Factorial(0), которое определено явно и равно 1. Любое рекурсивное описание должно содержать явное определение для некоторых значений аргумента (или аргументов), так как иначе процесс сведения оказался бы бесконечным. Таким образом при рекурсивном описании необходимо наличие базовой части описания, которая обеспечивала бы завершение рекурсивных вызовов функции (процедуры).

Рекурсивное обращение можно рассмотреть на примере вычисления определенного двойного интеграла по формуле трапеций. Точность этого приближения тем выше, чем больше число участков разбиения n. Увеличивая число n, можно достигнуть заданной точности. Если, допустим, функция TRAP вычисляет интеграл по методу трапеций при заданном числе интервалов N и А, В — пределы интегрирования, а FN — функция вычисления подынтегрального выражения, вычисление двойного интеграла можно осуществить с помощью следующего рекурсивного обращения к функции TRAP:

J := TRAP (N1, A1, B1, TRAP (N2, A2, B2, FN));

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

Пример 3.1.

Function HighFactor(N1 ,N2:lnteger):lnteger;

Рекурсия и рекурсивные алгоритмы

Цель лекции: изучить понятие, виды рекурсии и рекурсивную триаду, научиться разрабатывать рекурсивную триаду при решении задач на языке C++.

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

Рекурсия – это определение объекта через обращение к самому себе.

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

Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров . Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n , то есть имеет место зависимость: Sn=Sn-1+n . Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу.

При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров . Такая организация обращений называется косвенной рекурсией. Например, поиск максимального элемента в массиве размера n можно осуществлять как поиск максимума из двух чисел: одно их них – это последний элемент массива, а другое является максимальным элементом в массиве размера (n-1) . Для нахождения максимального элемента массива размера (n-1) применяются аналогичные рассуждения. В итоге решение сводится к поиску максимального из первых двух элементов массива.

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

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

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

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

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

Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии

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

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

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

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

Будем использовать следующие обозначения для конкретного входного параметра D :

R(D) – общее число вершин дерева рекурсии,

RV(D) – объем рекурсии без листьев ( внутренние вершины ),

RL(D) – количество листьев дерева рекурсии,

HR(D) – глубина рекурсии.

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

Тогда полное дерево рекурсии для вычисления пятого члена последовательности Фибоначчи будет иметь вид ( рис. 34.1):

Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины.

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

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

Я думаю, что тем, кто пытается постигнуть концепцию рекурсии, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 1000 слов, и ставлю цель писать 100 слов каждый раз, когда сажусь за работу. Получается, что в первый раз я напишу 100 слов и оставляю 900 слов на потом. В следующий раз я напишу ещё 100 слов, а оставлю 800. Я буду продолжать, пока не останется 0 слов. Каждый раз, я частично решаю проблему, а оставшаяся часть проблемы уменьшается.

Работу над статьей можно представить в виде такого кода:

Также, этот алгоритм можно реализовать итеративно:

Если рассматривать вызов функции write_words(1000) в любой из этих реализаций, вы обнаружите, одинаковое поведение. На самом деле, каждую задачу, которую можно решить с помощью рекурсии, мы также можем решить с помощью итерации (циклы for и while ). Так почему же стоит использовать именно рекурсию?

Почему рекурсия?

Хотите верьте, хотите нет, но с помощью рекурсии некоторые проблемы решить легче, чем с помощью итерации. Иногда рекурсия более эффективна, иногда более читаема, а иногда просто быстрее реализуется. Некоторые структуры данных, такие как деревья ― хорошо подходят для рекурсивных алгоритмов. Существуют языки программирования, в которых вообще нет понятия цикла — это чисто функциональные языки, такие как Haskell, они полностью зависят от рекурсии для итеративного решения задач. Я хочу сказать, что программисту не обязательно понимать рекурсию, но хороший программист, просто обязан в этом разбираться. Более того, понимание рекурсии сделает вас отличным «решателем» проблем, не только в программировании!

Суть рекурсии

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

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

В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа. Это немного надуманный пример, но если предположить, что я уже решил задачу f(900) (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).

Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:

Как будет выглядеть выполнение такой функции? Возьмём для примера fib(4) :

В процессе рекурсивного решения задачи полезно повторять мантру: «Притворяйся, пока это не станет правдой», то есть делай вид, что ты уже решил более простую часть задачи. Затем попытайся уменьшить большую часть задачи, чтобы использовать решение упрощённой части. Подходящая для рекурсии задача, на самом деле должна иметь небольшое количество простых частей, которые нужно решить явно. Другими словами, метод сокращения до более простой задачи может быть использован для решения любого другого случая. Это можно проиллюстрировать на примере чисел Фибоначчи, где для определения fib(n) мы действуем, как будто мы уже рассчитали fib(n-1) и fib(n-2). В тоже время мы рассчитываем, что эти каскады и упрощения приведут к более простым случаям, пока мы не достигнем fib(0) и fib(1) , которые имеют фиксированные и простые решения.

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

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

  1. Упорядочить данные
  2. Решить малую часть проблемы
  3. Решить большую часть проблемы

Как я уже говорил, я думаю, что для обучения полезно приводить пример, но помните, что рекурсивный подход зависит от конкретной задачи. Поэтому старайтесь сосредоточиться на общих принципах. Мы рассмотрим простой пример с реверсом строки. Мы напишем функцию reverse, которая будет работать так: reverse(‘Hello world’) = ‘dlrow olleH’ . Я рекомендую вернуться назад и посмотреть, как эти шаги применяются к функции Фибоначчи, а затем попробовать применить их на других примерах (в интернете можно найти много упражнений).

Упорядочивание данных

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

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

0, 1, 2, …, n для чисел (т.е. для int данных d, степень(d) = d)

[], [■], [■, ■], …, [■, … , ■] для списков (len = 0, len = 1, …, len = n и т.д. для списка d, степень(d) = len(d))

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

Решаем малую часть проблемы

Как правило это самая лёгкая часть. После того, как мы определились с порядком, мы должны выделить в нём самые маленькие элементы, и решить, как мы будем обрабатывать их. Обычно, можно найти очевидное решение: в случае reverse(s) , как только мы дойдём до len(s) == 0 , имея при этом reverse(») , это будет знаком, что мы нашли ответ, потому что реверс пустой строки ничего не даст, т.е. нам вернётся пустая строка, так как у нас нет символов, которые можно перемещать. Если мы знаем решение для базового случая, и мы знаем порядок, то для нас, степень сложности решения общего случая, уменьшается в зависимости от степени сложности данных, которыми мы оперируем, приближаясь к базовым случаям. Мы должны быть внимательны, чтобы не пропустить ни одного базового случая: они и называются базовыми, потому что образуют основу порядка. Пропуск маленького шага считается распространённой ошибкой в сложных рекурсивных задачах, и приводит к бессмысленным данным или ошибкам.

Переходим к общим случаям

На этом этапе мы обрабатываем данные двигаясь вправо, то есть в сторону высокой степени. Как правило, мы рассматриваем данные произвольной степени, и ищем способ решения проблемы, упрощая её до выражения, представляющего ту же проблему, но в меньшей степени. Например, в случае с числами Фибоначчи мы начали с произвольного значения n и упростили fib(n) до fib(n-1) + fib(n-2) , что является выражением, содержащим два экземпляра той же задачи, но в меньшей степени (n-1 и n-2, соответственно).

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

где string[-1] соответствует последнему символу, а string[:-1] соответствует строке без последнего символа (это питонизм). Последний член функции reverse(string[:-1]) , и является нашей исходной задачей, но он оперирует со строкой длины n-1. Таким образом, мы выразили нашу исходную задачу в решении той же задачи, но в уменьшенной степени.

Применив это решение к функции reverse , мы получаем следующее:

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

Напутствие

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

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

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

Рекурсивные алгоритмы

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

Рекурсивные алгоритмы

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

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

Рекурсию возможно применять, когда есть возможность выделения подобной самой себе задачи. В качестве примера можно привести задачу «Ханойские башни». Она содержит следующую постановку задачи. Монахи одного из буддийских монастырей перекладывают кольца в течение примерно уже тысячи лет. У них есть три пирамиды, на которые одеты кольца различных размерных величин. Изначально шестьдесят четыре кольца располагались надетыми на первую из пирамид в порядке убывания их размеров. Задачей монахов было перекладывание всех колец с исходной пирамиды на следующую, при соблюдении одного условия, перекладываемое кольцо не допускается класть на кольцо, размеры которого меньше. При операции перемещения колец допускается использование всех трёх пирамид. Скорость перекладывания колец монахами составляет одно кольцо в секунду. Когда они завершат свою задачу, придёт конец света. В рекурсивном варианте решение задачи будет выглядеть следующим образом. Алгоритм перемещения башни переместит необходимое число колец из пирамиды «источника» на пирамиду «приёмник» применяя «запас» в виде третьей пирамиды. При количестве колец равном одному, алгоритм будет следующим: переместите кольцо из источника в приёмник. Конец.

Попробуй обратиться за помощью к преподавателям

Если число колец больше:

  1. Используя рекурсию переместите все кольца, за исключением одного, из источника в запас, применяя приёмник в качестве запаса.
  2. Переместите последнее кольцо из источника в приёмник.
  3. Переместите все кольца из запаса в приёмник, применяя источник в качестве запаса.

Рекурсивные алгоритмы в программировании

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

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

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

Задай вопрос специалистам и получи
ответ уже через 15 минут!

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

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

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

Рекурсивные алгоритмы в других областях

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

Рекурсивные алгоритмы присутствуют также в области лингвистики. Это, например, могут быть языковые возможности создавать вложенные конструкции и предложения. Например, исходное предложение «кошка поймала мышь» можно расширить, применяя рекурсивный алгоритм, до «Вася понял, что кошка поймала мышь». Затем «Лиза узнала, что Вася понял, что кошка поймала мышь» и так можно продолжать бесконечно. Рекурсивный алгоритм можно считать универсальным лингвистическим методом, который есть в любом естественном языке. Но существует мнение, что в некоторых языках Амазонии свойство рекурсии не заложено изначально.

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

Читать еще:  Не включается безопасный режим
Ссылка на основную публикацию
Adblock
detector