Как работает рекурсия в программировании

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

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

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

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

Узнай, какие ИТ - профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес

Павел Симонов

Исполнительный директор Geekbrains

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

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов

Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно

pdf 3,7mb

doc 1,7mb

Уже скачали 31974

Если речь идет о статье, то код может выглядеть следующим образом:

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 простых случаев, при которых нет необходимости в дальнейшем разборе, т. е. либо когда была произведена обработка всей совокупности составляющих, либо когда первый элемент является искомым.

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

Дарим скидку от 60%
на обучение «Инженер-программист» до 01 декабря

Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей

Забронировать скидку

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

начало; 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

конец; вернуть результат

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

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

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

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

Только до 25.11

Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней

Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы получить файл, укажите e-mail:

Введите e-mail, чтобы получить доступ к документам

Подтвердите, что вы не робот,
указав номер телефона:

Введите телефон, чтобы получить доступ к документам

Скачать подборку бесплатно pdf 2,5mb

Уже скачали 52300

Я подтверждаю согласие на обработку персональных данных.

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

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

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

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])

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

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

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

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

Мы рассмотрели все нюансы рекурсии в программировании для чайников. Теперь вы знаете, что это – лёгкий и понятный метод написания кода. Есть задачи, для которых лучше всего применять именно рекурсивный подход. Такой код можно написать и итеративно, посредством структуры данных «стек».

Автор статьи:

Редакция сайта GeekBrains Шеф-редактор раздела Программирование