Что такое рекурсия в информатике

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

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

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

Используется второй случай теоремы: \(T^_n = \Theta(n^ <\log_b a>\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) = 3\cdot (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
\)

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

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

Источник

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

Feb 22, 2019 · 8 min read

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

Я думаю, что тем, кто пытается постигнуть концепцию рекурс и и, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 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) :

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

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

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

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

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

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

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

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

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

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

Напутствие

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

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

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

Источник

Рекурсия. Занимательные задачки

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

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

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

Задачи

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

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

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

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

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

Задача по приведению рекурсии к итеративному подходу симметрична.

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

Более подробно с этим можно познакомиться тут

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

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня

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

Поехали! Решения задач предоставлены на языке Java.

A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.

Источник