Как работает рекурсия функции: на примере 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, если по сути того же результата можно достичь и итеративными алгоритмами?». Вопрос абсолютно резонный!
В некоторых ситуациях циклы действительно оказываются проще и даже эффективнее рекурсии. При этом они тоже вполне могут работать с рекурсивными структурами данных. Более того, часто рекурсивные функции требуют больше места и памяти, нежели итеративные, ведь они постоянно добавляют новые слои в стек памяти. Однако есть нюанс — производительность рекурсивных функций на порядок выше.
Но!
На освоение рекурсивных функций требуется время и определенные усилия. И далеко не всегда удается их правильно реализовать. А некорректная реализация часто делает рекурсию довольно медленной по причине того, что вычисления производятся чаще, чем это на самом деле необходимо. Поэтому очень важно начинать практиковаться в реализации рекурсивных функций с максимально простых и даже примитивных задач, постепенно повышая сложность и вложенность.
С другой стороны, написание итеративных функций — это в большинстве случаев более громоздкий и сложный код. Взгляните, как выглядит итеративная функция для вычисления факториала (числа, умноженного на предыдущее число):
А вот так выглядит рекурсивная функция:
Разница очевидна, не так ли?
Курс "Python"
Хочешь получить обучение от Дмитрия Жарикова?
На курсе вы научитесь:
- Основам основ: «Алгоритмы + структуры данных = программы»
- Алгоритмам работы с языком программирования Python
- Разработке приложений с графическим интерфейсом
- Добавлению их к себе в портфолио!
