Введение в рекурсию OTUS
2026-03-10 01:02 Diff
https://otus.ru/journal/vvedenie-v-rekursiju/

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

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

Определение

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

Рекурсия – вызов функцией самой себя. Такие функции называются рекурсивными. Они работают внутри друг друга.

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

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

Для чего требуется

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

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

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

  • физике;
  • биологии;
  • лингвистике;
  • архитектуре.

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

Отличие от цикла

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

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

Этот процесс может быть объяснен простыми словами: инструкция с пунктом «Вернись к пункту 1» – это цикл, инструкция с пунктом «Прочитай инструкцию снова» – recursion.

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

О прерывании

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

Обычно путем выхода выступает какое-то условие, которое проверяется в самом начале выполнения заданной функции. Если оно выполняется, команда снова вызывает сама себя, в противном случае – выдается какое-то значение, которое отдается предыдущему «соседу», после чего операция закрывается.

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

Разновидности

Как работает рекурсия, понятно. Такие функции могут быть разных видов:

  1. Прямая. Она будет вызывать сама себя напрямую. Функция А вызывает функцию А, но с другими аргументами.
  2. Косвенная. Она действует через «третью» функцию. Команда А вызывает операцию В, а та снова обращается к команде А. Подобный процесс тоже выступает в качестве рекурсивного, но он менее очевиден.

Также поддерживаются каскадные и линейные типы. В линейной экземпляр функции обращается сам к себе только один раз, в каскадной – несколько. Примером может служить расчет чисел Фибоначчи. Он относится к каскадному типу, потому что функция будет обращаться к себе дважды: для n-1 и n-2.

Преимущества и недостатки

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

К преимуществам относят следующие особенности:

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

Недостатки у рассматриваемой операции тоже есть. Принято выделять два минуса:

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

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

Что лучше использовать: цикл или рекурсию

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

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

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

Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!