Содержание

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

Рекурсия ( от латинского « recurso » — бегу назад, возвращаюсь) в сомом общем виде – это есть правило определения ( или построения ) некоторого объекта с использованием его же самого.

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

Пример 7. Вычисление с помощью одного из следующих алгоритмов:

a) если n=0, то 1.

иначе

б)

где = если x = y то z,

иначе .

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

Проиллюстрируем работу алгоритма б) для n=4:

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

Пример 8. Функция «91». Следующий интересный алгоритм при заданном n

вычисляет значение, равное 91 для всех и значение n-10 для остальных n.

если n>100, то n-10,

иначе

Пример 9. Игра « Ханойская башня ».

Имеется 3 основания : A,B,C. На основании A лежат кольца одно га другом в порядке убывания размеров. Необходимо переместить кольца на основание B с использованием « промежуточного » основания

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

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

Рекурсивный алгоритм игры очень интересен. Обозначим его именем Ханой с параметрами : n – число колец, X – исходное основание, Y – конечное, Z – промежуточное ( переменные X,Y,

Z могут, например, принимать значения A,B,C ). Условимся, что оператор ПЕРЕМЕСТИТЬ(X,Y) выполняет перемещение верхнего кольца с основания X на основание Y.

Алгоритм состоит всего из четырех строк :

Ханой(n, X, Y, Z).

Если n>0 , то выполнять 1,2,3.

  1. Ханой( n-1, X, Z, Y) ;

  2. ПЕРЕМЕСТИТЬ(

    X,Y);

  3. Ханой( n-1, Z, Y, X) ;

Выход.

Здесь единственное реальное действие выполняется оператором ПЕРЕМЕСТИТЬ(X,Y).

Число элементарных перемещений, выполняемых этим алгоритмом, составляет . Легенда, связанная с этой древней игрой, гласит, что конец света совпадает с концом перенесения 64-х колец. Соответствующее количество перемещений ; это потребует 10 миллионов лет на сверхбыстродействующей ЭВМ.

Рекомендации по составлению рекурсивных алгоритмов.

Разработка рекурсивного алгоритма обычно состоит из 3-х основных этапов:

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

б) поиск простейшего ( тривиального ) случая и его разрешение. Как правило, это решения задачи при размерности, равной 0 или 1 и т.п.;

в) определение правила сведения задачи размерности n к задаче размерности n-1 с помощью рекурсии. Это правило обычно является основной частью приведенного алгоритма.

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

Лекция 2. РЕКУРСИВНЫЕ ФУНКЦИИ

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

Рекурсия в самом общем виде – это есть правило определения ( или построения ) некоторого объекта с использованием его же самого.

Дадим некоторые важные определения.

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

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

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

.

Для первоначального ознакомления с рекурсивными функциями рекомендуется литература [ 1,4,8 ]. Для более полного изучения можно воспользоваться монографией А.И. Мальцева [ 5 ] или Р. Петер [ 6 ]. Книга [ 6 ] вместе с тем написана достаточно просто и понятно даже для неподготовленного читателя.

Рекурсивный алгоритм — Большая Энциклопедия Нефти и Газа, статья, страница 1

Cтраница 1

Рекурсивные алгоритмы особенно подходят для задач, где обрабатываемые данные определяются в терминах рекурсии. Однако это не означает, что такое рекурсивное определение данных гарантирует бесспорность употребления для решения задачи рекурсивного алгоритма. Фактически объяснение концепций рекурсивных алгоритмов на неподходящих для этого примерах и вызвало широко распространенное предубеждение против использования рекурсий в программировании; их даже сделали синонимом неэффективности.  [1]

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

Иногда рекурсивные алгоритмы менее эффективны, чем эквивалентные итерационные, чаще всего из-за накладных расходов, обусловленных вызовом процедуры, но для быстрой сортировки эффект незначителен — рекурсии не происходит в самом внутреннем цикле. В некоторых упражнениях вопросы эффективности рассматриваются, когда базовый алгоритм имеется под рукой.  [3]

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

Этот рекурсивный алгоритм использует системный стек для отслеживания текущей вершины графа, что позволяет правильно осуществить возвращение, наткнувшись на тупик. Вы можете построить аналогичный нерекурсивный алгоритм самостоятельно, воспользовавшись стеком для занесения туда и удаления пройденных вершин графа.  [5]

Реализация рекурсивного алгоритма для двоичного дерева в языке Модула-2 особенно проста благодаря применению типа указателя, динамических элементов данных и рекурсивных обращений к процедурам.  [6]

Идея рекурсивного алгоритма не вызывает трудностей.  [7]

Насколько эффективен рекурсивный алгоритм. Сможем ли мы подсчитать его эффективность, если будем знать, что алгоритм непосредственного вычисления квадратичен, разбиение входных данных логарифмично, а объединение решений линейно ( все в зависимости от размеров входных данных) 4, и что входные данные разбиваются на восемь частей, размер каждой из которых равен четверти исходного. Эту задачу не так-то легко решить, не очень-то понятно даже, как к ней приступать. Однако оказывается, что анализ алгоритмов вида разделяй и властвуй очень прост, если шаги Вашего алгоритма поставлены в соответствие шагам предложенного выше общего алгоритма этого вида: непосредственное вычисление, разбиение входа, некоторое количество рекурсивных вызовов и объединение полученных решений.  [8]

Лемма 5.2 Рекурсивный алгоритм разделяй и властвуй решения задачи о ханойских башнях дает решение, приводящее к 2 — 1 перемещениям.  [9]

С помощью рекурсивного алгоритма не создается никаких копий исходного массива V; все действие совершается пересылкой для указания того, какая часть V должна быть реорганизована на данном шаге. Эго означает, что единственной областью внешней памяти, необходимой для быстрой сортировки, является область для стека границ массива, описывающих еще не подвергшиеся разбиению множества. Легко показать, что если на каждом шаге быстрая сортировка осуществляется сначала с меньшим подмножеством, а потом с большим, то стек никогда не будет глубже, чем 1о § 2 N. Даже для N 106 Iog2 N 20, поэтому такой дополнительный объем требуемой памяти незначителен.  [10]

Архитектура специального программного обеспечения.  [11]

ФОРТРАН программирование рекурсивных алгоритмов требует использования специальных приемов, усложняющих программу.  [12]

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

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

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

Страницы:      1    2    3    4

Рекурсивное программирование. Рекурсия достаточно часто встречается… | by Evgeny Vladimirovich | NOP::Nuances of Programming

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

От рекурсии может заболеть голова

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

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

write_words(words_left):
if words left > 0:
write_100_words()
words_left = words_left - 100
write_words(words_left)

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

write_words(words_left):
while words_left > 0:
write_100_words()
words_left = words_left - 100

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

Я пишу статью рекурсивно

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

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

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

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

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

Предположим, у нас есть фактические данные определённого типа, назовём их 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(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return fib(n-1) + fib(n-2)

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

Визуализация древа рекурсии, показывающая рекурсивное вычисление, которое приводит к fib(4) = 3. Обратите внимание, что вычисление сначала выполняется в глубину.

В процессе рекурсивного решения задачи полезно повторять мантру: «Притворяйся, пока это не станет правдой», то есть делай вид, что ты уже решил более простую часть задачи. Затем попытайся уменьшить большую часть задачи, чтобы использовать решение упрощённой части. Подходящая для рекурсии задача, на самом деле должна иметь небольшое количество простых частей, которые нужно решить явно. Другими словами, метод сокращения до более простой задачи может быть использован для решения любого другого случая. Это можно проиллюстрировать на примере чисел Фибоначчи, где для определения 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? Мы могли бы сделать реверс строки, переместив всё, кроме последнего символа, а затем вставить этот последний символ в начало. В коде:

reverse(string) = reverse(string[-1]) + reverse(string[:-1])

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

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

reverse(string):
if len(string) == 0:
return ''
else:
return string[-1] + reverse(string[:-1])
Визуализации рекурсивной функции reverse

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

Напутствие

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

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

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

На этом всё, спасибо за внимание.

Перевод статьи Tom Grigg: Recursive Programming

Временная сложность рекурсивных функций [Основная теорема] · YourBasic

yourbasic.org

Часто можно вычислить временную сложность рекурсивной функции. формулируя и решая рекуррентное соотношение.

  • Рекуррентное отношение (базовый пример)
  • Бинарный поиск
  • Основная теорема
  • Анализ без повторения

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

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

Повторяющееся отношение

В качестве введения покажем, что следующая рекурсивная функция имеет линейную временную сложность.

 // Сумма возвращает сумму 1 + 2 + ... + n, где n >= 1.
func Sum(n int) int {
    если п == 1 {
        вернуть 1
    }
    вернуть n + сумма (n-1)
}

Пусть функция T( n ) обозначает число элементарных операций, выполняемых вызовом функции Сумма(n) .

Мы определяем два свойства T( n ).

  • Поскольку Sum(1) вычисляется с использованием фиксированного числа операции к 1 , T(1) =  k 1 .
  • Если n  > 1 функция будет выполнять фиксированное число операций k 2 , а кроме того, он сделает рекурсивный вызов Sum(n-1) . Этот рекурсивный вызов выполнит T( n -1) операций. Итого получаем Т( n ) =  k 2  + T( n -1).

Если мы ищем только асимптотическую оценку временной сложности, нам не нужно указывать фактические значения константы k 1 и  к 2 . Вместо этого положим k 1 = k 2  = 1. Чтобы найти временную сложность функции Sum то можно свести к решению рекуррентного соотношения

  • T(1) = 1,  (*)
  • T( n ) = 1 + T( n -1), когда n  > 1.  (**)

Повторно применяя эти соотношения, мы можем вычислить T( n ) для любого положительного числа n .

T( n ) = (**) 
1 + T( n -1) = (**) 
1 + (1 + T( n -2)) = 2 + T( n -2) = (**) 
2 + (1 + T( n -3)) = 3 + T( n -3) = … 
k + T( n 9(*)

Бинарный поиск

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

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

 // Find возвращает наименьший индекс i, при котором x

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

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

  • T(1) = 1,  (*)
  • T( n ) = 1 + T( n /2), когда n  > 1.  (**)

Уравнение (**) фиксирует тот факт, что функция выполняет постоянную работу (тот самый) и один рекурсивный вызов фрагмента размером 9 0027 н /2.

(На самом деле срез может также содержать n /2 + 1 элементов. Нас это не беспокоит, поскольку мы ищем только асимптотическую оценку.)

Опять же, можно найти решение повторной подстановкой.

T( n ) = (**)
1 + T( n /2) = (**)
1 + (1 + T( n /4)) = 2 + T( n /4) = (**)
2 + (1 + T( n /8)) = 3 + T( n /8) = …
k + T( n /2 k ) = …
log n + T( n /2 log  n ) = log n + T(1) = (*)
log = n + 1 (журнал n ).

Основная теорема

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

Пусть a ≥ 1 и b > 1 — константы, пусть f( n ) — функция, и пусть T( n ) будет функцией над положительными числами определяется повторением

T( n ) = aT( n /b) + f( n ).

Если f( n ) = Θ( n d ), где d ≥ 0, тогда

  • T( n ) = Θ( n d ) если a < b d ,
  • T( n ) = Θ( n d log  n ) если a = b d ,
  • T( n ) = Θ( n log b a ) если a > b d .

Пропустим доказательство. Это не сложно, но долго. На самом деле, вы можете использовать повторную замену так же, как и в предыдущие примеры.

Давайте проверим, что основная теорема дает правильное решение к повторению в примере с бинарным поиском. В этом случае а = 1, б = 2, и функция f( n ) = 1. Отсюда следует, что f( n ) = Θ( n 0 ), т. е. d = 0. Мы видим, что a = b d , и можем использовать второй пункт списка основной теоремы, чтобы заключить, что

T( n ) = Θ( n 0 log n ),

правильно.

Анализ без повторения

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

Рассмотрим этот граф с 36 (синими) вершинами и 3 непересекающихся компонента связности.

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

  Алгоритм  DFS(G, v)
     , если  v уже посещено
          возврат 
    Отметить v как посещенный.
    // Выполняем некоторую операцию над v.
      для  все соседи x из v
        DFS(G, х)

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

Чтобы вычислить временную сложность, мы можем использовать количество вызовов DFS . как элементарная операция: оператор if и операция отметки выполняется в постоянное время, а цикл for делает один вызов DFS для каждой итерации.

  • Перед запуском алгоритма все |V| вершины должны быть помечены как непосещенные. Это занимает Θ(|V|) времени.
  • Пусть E’ будет набором всех ребер компонента связности, посещаемых алгоритмом. Алгоритм делает два вызова DFS для каждого ребра { u ,  v } в E’: один раз, когда алгоритм посещает соседей и , и один раз, когда он посещает соседей v .

Следовательно, временная сложность алгоритма равна Θ(|V| + |E’|).

Другие примеры

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

Поделиться этой страницей:

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

..

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

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

Правила

Чтобы алгоритм был классифицирован как рекурсивный, он должен следовать нескольким правилам, показанным ниже:

  1. должен иметь базовый случай
  2. должен изменить свое состояние и перейти к базовому варианту
    3. .
  3. должен вызывать себя рекурсивно

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

Базовый случай

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

Изменение состояния

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

Рекурсия

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

Реализация

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

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

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

Рекурсивный алгоритм может быть реализован как функция, метод или класс.

Посмотреть полную реализацию рекурсивного алгоритма можно здесь.

Динамическое программирование

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

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

  • табулирование
  • запоминание

Таблица

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

Когда подзадачи должны быть решены хотя бы один раз, этот подход работает лучше, чем запоминание.

Посмотреть пример табуляции здесь.

Мемоизация

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

Посмотрите пример подхода с мемоизацией здесь.

Заключение

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

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

Рекурсия — Информатика уровня A

Введение

Что такое рекурсия?

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

Чтобы быть успешно рекурсивной, рекурсивная функция должна подчиняться 3 правилам:

3 правилам рекурсии

  • Алгоритм должен иметь базовый случай
  • Алгоритм должен работать в направлении базового случая
  • Алгоритм должен вызывать себя рекурсивно

Зачем использовать рекурсию?

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

Стопки и разматывание

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

Компилятор и стек – что он должен делать?

 

Исключения переполнения стека и ограничения глубины рекурсии

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

Видео

Тема Видео

Не удается получить доступ к YouTube? Щелкните здесь, чтобы просмотреть версию для Google Диска.

Факториал

Факториал Пример

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

Факториал числа вычисляется путем его умножения на все меньшие положительные целые числа.

Факториал 5 равен 5*4*3*2*1 = 120

 

Фрактальное дерево

Визуальная демонстрация фрактального дерева

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

 

Обход файлов

Обход дерева файлов/папок

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

Алгоритму предоставляется имя папки/диска, и файлы/папки исследуются рекурсивно.

Двоичный поиск

Двоичный алгоритм поиска

Двоичный алгоритм поиска может быть запрограммирован с использованием рекурсивного алгоритма.

Brute Force

Brute Force Password Hacker – For Loop Version

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

  1. Если максимальная длина пароля изменена с 4 на большее число, вам потребуется еще один вложенный цикл для каждого дополнительного возможного символа.
  2. Это немного медленнее, чем рекурсивная версия ниже, и было бы намного медленнее, если бы использовался более длинный пароль / дополнительные возможные символы.

Brute Force Password Hacker – рекурсивная версия

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

Задачи

Задачи по программированию

Задание 1 – Сумма списка чисел

Напишите программу, которая складывает все числа в списке

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

900 Последовательность Фибоначчи для заданного числа.

Задание 3 – Варианты питания

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

  • Пицца
  • Спагетти
  • Салат
  • Карри
  • Гамбургер

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

Задача 4 – Поиск файлов

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

Задание 5. Адаптация программы обхода дерева

Красочная реализация алгоритма рекурсивного дерева

  • Адаптировать программу так, чтобы листья ветки были зелеными
  • Адаптировать программу так, чтобы ветки постоянно становились тоньше

 

Эта страница должна помочь вам начать работу.

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

Список других распространенных рекурсивных задач

Ресурсы

Ресурсы

Учитель Slideshow Document

Что представляет собой рекурсионное компьютерное видео

Оптимизация хвостовых вызовов / переполнение стека (задача расширения)

Онлайн -визуализатор Python

ISAAC Compuforce Science Page

Теория Ревизионная деятельность — Требования 9000 2

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

No related posts.