2 858 
Оставить комментарий
Сохранить статью:
В статье рассказывается:
- Рекурсия в программировании простыми словами
- Примеры алгоритмов рекурсии в программировании
- Вычисление чисел Фибоначчи
- Рекурсивная стратегия
-
Пройди тест и узнай, какая сфера тебе подходит:
айти, дизайн или маркетинг.Бесплатно от Geekbrains
Пытаясь примитивно объяснить рекурсию в программировании, многие ошибочно представляют ее по аналогии с зацикленным видеофрагментом типа гифок. И потому возникают вопросы о целесообразности ее использования, ведь программный код по сути прописывает пошаговые действия. Так зачем же нужен этот «уроборос»?
Но если все же вернуться к терминам программирования, то рекурсию можно трактовать как функцию, которая вызывает сама себя. И это объяснение кажется почти парадоксальным: ведь как найти решение проблемы, используя ее же решение?! И тем не менее, рекурсия в программировании используется весьма активно. И вот почему.
Что такое рекурсия в программировании простыми словами
Рекурсия представляет собой методологию решения проблем, в которой вы выполняете задачу по частям, не рассматривая ее целиком. При этом задача уменьшается или становится проще. Таким образом, рекурсия является не просто практикой в программировании, а целым философским подходом.
Рекурсию можно использовать и для достижения простейших бытовых целей. К примеру, перед вами стоит задача написания 500 слов. В этом случае вы можете поставить себе цель создавать по 50 лексем всякий раз, когда начинаете работать. Вначале вы пишете это их количество, остается 450.
Далее вы проделываете то же самое, и следующая задача – уже 400 слов. Тем самым при каждом подходе вы не решаете проблему полностью, но уменьшаете ее объем.
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Скачивайте и используйте уже сегодня:
Топ-30 самых востребованных и высокооплачиваемых профессий 2023
Поможет разобраться в актуальной ситуации на рынке труда
Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка
Только проверенные нейросети с доступом из России и свободным использованием
ТОП-100 площадок для поиска работы от GeekBrains
Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽
Если речь идет о статье, то код может выглядеть следующим образом:
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). Но в чем же тогда преимущество данного метода?
Дело в том, что существуют проблемы, которые гораздо проще разрешить посредством рекурсии. В некоторых случаях она показывает повышенную эффективность, в других — бо́льшую читаемость, а в определенных ситуациях банально занимает меньше времени при реализации. Есть такие структуры данных, которые сами по себе очень подходят для рекурсивных алгоритмов (например, деревья).
Некоторые языки программирования не предполагают наличие цикла. Они являются сугубо функциональными и всецело зависят от применения рекурсии при итеративном решении проблем.
В принципе, программист может и не понимать рекурсии. Однако специалист высокого уровня все же должен осознавать суть данной методики. Плюс ко всему, вы сможете применять этот подход в других областях, эффективно решая различные задачи.
Итак, рекурсия в программировании предполагает дифференцирование больших задач на более мелкие. Выполняя один шаг, вы уменьшаете основную проблему и после этого повторяете аналогичное действие. В конечном итоге проблема уменьшается настолько, что остается выполнить одно простое действие, которое принято называть базовым случаем.
Скачать файлТаким образом простейшее решение базового случая, в совокупности со всеми действиями, которые вы осуществили перед этим, представляет собой разгадку основной проблемы.
Примеры алгоритмов рекурсии в программировании
Понять, что такое рекурсия в программировании, можно с помощью простых примеров. При помощи этого алгоритма проблема разделяется на составляющие, которые структурно представляют собой такие же задачи, как и основная. Единственное отличие — они являются упрощенными по сравнению с исходной проблемой. Чтобы решить эти подзадачи, функция вызывается рекурсивно.
Скажем, если стоит цель обработки массива, то во многих случаях ее можно редуцировать к последовательной однотипной обработке его составляющих. Исходя из определения рекурсии в программировании, становится очевидным, что разделение осуществляется вплоть до момента, когда эти части не станут наиболее легкими. Иными словами, подзадачи должны быть настолько элементарными, чтобы их можно было решить, не прибегая к очередному упрощению.
начало; search(array, begin, end, element)
; выполняет поиск элемента со значением element в массиве array между индексами begin и end
если begin > end
результат := false; элемент не найден
иначе если array[begin] = element
результат := true; элемент найден
иначе
результат := search(array, begin+1, end, element)
конец; вернуть результат
Тем самым алгоритм дифференцирует исходный массив на 2 составляющие — первый элемент и массив из оставшихся частей. Происходит выделение 2 простых случаев, при которых нет необходимости в дальнейшем разборе, т. е. либо когда была произведена обработка всей совокупности составляющих, либо когда первый элемент является искомым.
В алгоритме поиска можно дифференцировать массив и другим способом, к примеру, на две равные части. Однако такой подход обычно менее результативен. Когда массив отсортирован, его имеет смысл разделять на две одинаковые части, ведь на каждом шаге численность обрабатываемых данных можно разобрать на два фрагмента.
на обучение «Инженер-программист» до 28 апреля
Двоичный поиск в массиве осуществляется после того, как была произведена его сортировка. На любом из этапов работы происходит сравнение между искомым элементом и значением, которое располагается в средней части массива. После получения результатов такого сравнения левая или правая части могут быть отброшены. Например:
начало; binary_search(array, begin, end, element)
; выполняет поиск элемента со значением element
; в массиве, упорядоченном по возрастанию, массиве array
; между индексами begin и end
если begin > end
конец; вернуть false — элемент не найден
mid := (end + begin) div 2; вычисление индекса элемента посередине рассматриваемой части массива
если array[mid] = element
конец; вернуть true (элемент найден)
если array[mid] < element
результат := binary_search(array, mid+1, end, element)
иначе
результат := binary_search(array, begin, mid, element)
конец; вернуть результат
Вычисление чисел Фибоначчи
Ряд чисел Фибоначчи определяется рекуррентным соотношением. Проще говоря, каждое последующее число вычисляется на основе предыдущих:
F0=0,F1=1,Fn=Fn−1+Fn−2,n>2.
начало; fibonacci(number)
если number = 0
конец; вернуть 0
если number = 1
конец; вернуть 1
fib_1 := fibonacci(number-1)
fib_2 := fibonacci(number-2)
результат := fib_1 + fib_2
конец; вернуть результат
Рекурсивная стратегия
В зависимости от того, какую задачу необходимо решить, стратегия рекурсивного метода может отличаться. Вместе с тем существует общая тактика, которую можно использовать в качестве ориентира:
Упорядочивание данных
Это фундаментальный этап решения задач при помощи рекурсивного метода, однако многие пренебрегают тщательностью его выполнения. Неважно, какие именно данные используются — числа, строки, списки, бинарные древа или же люди, – вам в любом случае следует отыскать оптимальный порядок элементов.
ТОП-100 площадок для поиска работы от GeekBrains
20 профессий 2023 года, с доходом от 150 000 рублей
Чек-лист «Как успешно пройти собеседование»
Это не только позволит лучше понять задачу, но и сделает ее решение значительно проще. В зависимости от текущей проблемы этот порядок будет отличаться. Однако сначала рекомендуется рассмотреть самые очевидные варианты сортировки.
Если речь идет о числах, то можно произвести упорядочивание по величине, о строках и списках — по длине, бинарные древа систематизируются по глубине. Если же выстраиванию подвергаются люди, то вариантов гораздо больше: по росту, по весу, по специализации и т. д. При этом выбранный метод упорядочивания должен соответствовать тому, насколько сложной является проблема.
Вслед за тем, как вы осуществите упорядочивание данных, необходимо подумать об этом, как о чём-то, что вы можете сократить. Формализация порядка может выглядеть следующим образом:
0, 1, 2, …, n – для чисел (т. е. для int данных d, степень(d) = d);
[], [■], [■, ■], …, [■, …, ■] – для списков (len = 0, len = 1, …, len = n и т. д. для списка d, степень(d) = len(d)).
Идя справа налево, вы будете передвигаться от большой части задачи (скопления базовых случаев) к небольшим фрагментам (базовым случаям).
Решаем малую часть проблемы
Чаще всего данный этап является наиболее простым. Произведя упорядочивание, необходимо определить самые мелкие задачи, а затем выбрать способ работы над ними. Как правило, имеется возможность отыскать простейшее решение: в случае 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])
Перед программистами нередко встаёт проблема рассмотрения нескольких рекурсивных случаев, потому что данные определённого типа могут принимать различные формы. Однако это всецело зависит от самой задачи.
В качестве примера рассмотрим случай, при котором вы собираетесь сгладить список элементов, некоторые из которых сами могут являться такими же перечнями. Вам следует различать ситуации, когда объект, который вы вытаскиваете из списка, является отдельным элементом, и когда – подсписком. Это влечет за собой как минимум два самостоятельных рекурсивных случая.
Учтите, что невозможно улучшить навыки в рекурсии без практики. На просторах Сети вы можете отыскать сотни примеров различных задач, которые можно решить при помощи данного метода. Рано или поздно вы овладеете им, но при появлении каких-либо проблем вы всегда можете переключиться на итерацию.
Рекурсивный метод применим как в программировании, так и в быту. Если задача не подходит для такого решения, то ничего страшного. Набравшись опыта, вы станете быстрее понимать, какую проблему можно решить рекурсивно, а какую итеративно.
Мы рассмотрели все нюансы рекурсии в программировании для чайников. Теперь вы знаете, что это – лёгкий и понятный метод написания кода. Есть задачи, для которых лучше всего применять именно рекурсивный подход. Такой код можно написать и итеративно, посредством структуры данных «стек».
Разберем 11 самых важных жизненных вопросов
Только до 
Эксклюзивные лекции по основам программирования
