Как работает рекурсия функции: на примере Python

Итак, сегодня у нас не самая простая, но очень важная тема для тех, кто выбрал программирование как сферу деятельности. И в частности планирует или уже работает с языком программирования Python. 

Речь идет о рекурсии функции!

Мы постараемся объяснить ее максимально простыми и понятными словами, чтобы даже новички могли на базовом уровне понять, что это, как работает и зачем используется.

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

Что такое рекурсия: быстрое напоминание

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

Для начала предлагаем вам взглянуть на лист папоротника:

Что вы видите?

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

Еще один похожий пример — капуста романеско:

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

Но как вообще листья папоротника или капуста романеско вяжется с программированием? Давайте разбираться!

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

Как мы и сказали, рекурсивная функция — это функция, которая вызывает саму себя.

Посмотрим на более «житейском» примере, как это может работать в программировании.

Представьте, что вам нужно попасть в гардеробную, которая закрыта на ключ. Рядом с гардеробной стоит коробка, на которой написано, что ключ внутри. Вы открываете коробку, а внутри лежат еще коробки. А в них — еще. Как вам действовать, чтобы максимально быстро найти нужную коробку с ключом?

По большому счету есть два алгоритма действий:

В первом случае применяется цикл while. То есть, вы берете коробку, открываете ее, затем следующую и так до того самого момента, пока не найдете нужную вам коробку с ключом. Это так называемый итерационный (пошаговый) метод. В Python он может выглядеть следующим образом:

Так как у нас стоит задача с повторяющимися действиями, но меняющимися параметрами, мы можем использовать рекурсивный метод. То есть, решить задачу, используя ее же саму:

В этом примере summa(1) — это 1, summa(2) — это 2 + summa(1) и так далее. Данный алгоритм проще будет понять на следующей схеме:

И тут необходимо указать важную деталь. По большому счету оба алгоритма выполняют одну и ту же задачу — ищут «коробку с ключом». Более того, в данном случае у рекурсивного метода не будет особенного преимущества над итерационным. Однако рекурсия функции гораздо лучше подходит для решения сложных многоуровневых задач. Это будет быстрее, проще и понятнее. Но что еще важнее — рекурсивные решения проще поддерживать.

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

Продолжим рассматривать наш пример с summa(n). Есть два важнейших требования, без соблюдения которых алгоритм не будет работать:

• Базовый случай

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

• Рекурсия

Чтобы базовый случай в принципе состоялся, требуется передача измененных данных каждой новой вызванной функции. В нашем примере первый вызов n = 5, второй — 4 и так далее. И только когда n становится равным 1, рекурсия завершается.

Как работают рекурсивные алгоритмы

Что ж, теперь предлагаем немного отойти от наших бытовых примеров и переключиться непосредственно на программирование с Python. 

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

Рассмотрим рекурсивную функцию на примере summa(5). В компьютере хранятся данные о функции в виде блока, в котором в свою очередь установлено значение переменной n и код, который выполняется. Наглядно это выглядит следующим образом:

При выполнении функции summa(5) начинает вызывать summa(4). В это же время формируется новый блок и размещается над предыдущим: 

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

Далее summa(1) возвращает единицу, завершает работу и выходит из стека. В верхней части остается summa(2):

Теперь уже summa(2) продолжает выполнение с того момента, на котором остановилась. За ней — summa(3) и так далее до самого завершения стека.

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

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

Зачем рекурсия нужна

Вот тут у вас может возникнуть логичный вопрос: «А нужно ли вообще использовать рекурсию функции в Python, если по сути того же результата можно достичь и итеративными алгоритмами?». Вопрос абсолютно резонный!

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

Но!

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

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

А вот так выглядит рекурсивная функция:

Разница очевидна, не так ли?