Рекурсия

Рекурсия (recursion) — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга.

Известная шутка гласит: «Чтобы понять рекурсию, надо понять рекурсию».

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

Это работает так: функция A от единицы запускает функцию A от двойки, та — от тройки, и так далее, пока не будет высчитано нужное значение. Чтобы рекурсивный вызов закончился, нужно сразу прописать в функции A условие выхода из рекурсии: например, если получено какое-то значение, нужно не запускать функцию заново, а вернуть некоторый результат.

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

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

Кто пользуется рекурсией и зачем она нужна

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

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

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

Программисты пользуются рекурсией и ради забавы. Например, известная аббревиатура GNU расшифровывается как GNU is Not Unix – первая буква скрывает под собой ту же аббревиатуру. Это тоже рекурсия.

Отличия рекурсии от цикла

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

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

Простыми словами: инструкция с пунктом «Вернись к пункту 1» — это цикл, инструкция с пунктом «Прочитай инструкцию заново» — рекурсия.

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

Прерывание рекурсии

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

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

Например, если n > 1, то вызвать A(n-1). Иначе вернуть 1. Получается, что когда n станет меньше или равен единице, то A не запустится заново — очередной экземпляр просто вернет единицу. Остальные экземпляры получат нужный себе результат и тоже закроются по каскаду. Этот процесс называется обратным ходом рекурсии. А то, что было до него, — прямым ходом.

Количество открытых в итоге функций называется глубиной рекурсии.

Пример рекурсии: расчет чисел Фибоначчи

Известный пример рекурсивных расчетов — числа Фибоначчи. Каждое следующее число в ряду — сумма двух предыдущих, начиная с 1.

Получается так: 1, 1, 2, 3, 5, 8, 13, 21 и так далее. Использование рекурсии здесь — напрашивающийся и интуитивно понятный способ расчета:

• допустим, функция называется fibonacci(n) и рассчитывает n-е по счету число Фибоначчи;
• на первом шаге функция вызывает fibonacci(n-1) и fibonacci(n-2), то есть себя, но с другими аргументами, и складывает получившиеся результаты;
• новые вызовы будут делать то же самое, пока n не дойдет до единицы или нуля — это первое число Фибоначчи, и в таком случае функция вернет 1;
• предыдущий экземпляр функции получит два результата 1 — от единицы и нуля, сложит их и отправит «назад» к более ранним соседям;
• в итоге все вызванные функции получат от своих «потомков» ответ, сложат полученные значения и вернут их самой первой функции fibonacci(n);
• та сложит финальные значения, вернет результат и закроется.

Это только один простой пример; рекурсивных алгоритмов намного больше. Еще один известный — расчет факториала числа.

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

• Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.
• Расчет и изображение фракталов — конструкций, где более мелкие элементы повторяют более крупные. Яркие примеры фракталов — снежинка и лист папоротника.
• Обход ветвящихся структур данных, например графов и деревьев.
• Компьютерный анализ естественного языка, фраз и предложений.
• Поиск пути в лабиринте и построение маршрутов — к примеру, алгоритмы DFS и BFS.
• Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.
• Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.
• Операции с системами счисления, к примеру перевод чисел из одной в другую.

За пределами математики и информатики можно вспомнить много других примеров рекурсии: от самовозбуждения электронных схем до сказок «Тысячи и одной ночи».

Прямая и косвенная рекурсия

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

• Прямая вызывает сама себя напрямую. То есть функция A вызывает функцию A с другими аргументами.
• Косвенная действует через «третью» функцию. Функция A вызывает функцию B, а та в свою очередь снова вызывает функцию A. Это тоже рекурсия, просто менее очевидная.

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

Рекурсивный и итеративный процессы

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

В рекурсивном процессе все расчеты откладываются «на потом», как в примере с числами Фибоначчи. Конечный расчет делает тот экземпляр функции, который вызвали в последнюю очередь, а потом результаты по каскаду передаются предыдущим.

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

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

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

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

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

Наглядность. Некоторые задачи, вроде тех же чисел Фибоначчи или факториалов, — рекурсивные по самому своему определению. То же самое касается задач на ряды, фракталы и так далее. Решить такую задачу через рекурсию — один из наиболее наглядных и интуитивно понятных способов. Более того: люди пользуются рекурсией все время, даже просто когда разговаривают, и это лишний раз работает на интуитивное ее понимание.

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

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

Недостатки рекурсии

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

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

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

Чем пользоваться: рекурсией или циклом

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

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

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

Как начать работать с рекурсией

Концепт и примеры рекурсивных функций можно найти в любом учебнике по программированию. Обычно начинающим предлагают потренироваться на простых «классических» задачах вроде чисел Фибоначчи или расчета факториала. Затем можно переходить к более сложным заданиям: обход графа, анализ текста или что-либо еще. А какой язык выбрать — зависит от ваших предпочтений и пожеланий к отрасли.

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