Сегодня мы рассмотрим не простую, но очень важную тему для людей, избравших своей сферой деятельности программирования.
Речь идет о рекурсии функции!
Мы сделаем все возможное, чтобы донести до вас эту информацию максимально доступно. Так что разобраться в представленной нами информации смогут и начинающие.
Рекурсией в программировании называют такую функцию, которая способна вызвать себя из себя, но изменяя значение параметров. Возможно, пока это сложно осознать, поэтому мы попытаемся взглянуть на эту тему со стороны бытовых примеров. В качестве примера можем рассмотреть листок папоротника:
Что мы видим?
У нас есть одна «основная» ветка. Из нее разветвляется много подобных «основной» ветвей, но меньше. Из которых отходят еще меньшие ветки.
То есть, если мы воспринимаем «основную» ветвь как функцию, то видим, что из нее образуются подобные функции, только параметры у них изменились. В данной ситуации изменился размер.
Возможно привести еще один подобный пример – капуста романеско.
В целом, у природы много показательных иллюстраций рекурсии. Это явление часто используется и в других видах человеческой деятельности, таких, как живопись, музыка, архитектура и другие виды искусства.
Рекурсия – одновременно хаос и порядок.
Но как вообще это природное явление сочетается с кодингом и программированием? Разберемся!
Как уже было сказано, рекурсия функции – это функция, которая обращается к самой себе. Обратим внимание на жизненный пример, который может работать в программировании.
Представьте, что вам нужно зайти в закрытую комнату. Рядом находится коробка, на которой указано, что ключ находится в ней. Открываете коробку и чудо – внутри еще коробки. А у них еще коробки. И так будет продолжаться до определенного момента. Что же можно сделать, чтобы найти нужную коробку с ключом? Для этого существует два метода:
В первом случае вы примените цикл «while». То есть вы будете открывать коробку за коробкой и так пока не откроете ту самую нужную, в которой находится ключ. Этот метод называется итерационным или пошаговым.
def summa(n):
x = 0
for n in range(1, n+1):
x += n
return x
summa(5)
>>> 15
def summa(n):
if n == 1:
return 1
return n + summa(n-1)
summa(5)
>>> 15
В этом примере summa(1) – это 1, summa(2) – это 2 + summa(1) и так далее. Данный алгоритм проще будет понять на следующей схеме:
И здесь нужно обратить внимание на одну важную деталь. По большому счету, оба алгоритма выполняют одну и ту же задачу — ищут «коробку с ключом».
В общем, оба алгоритма работают и выполняют нужную нам задачу – ищут «коробку с ключом». К тому же, в таком случае метод рекурсии не будет иметь особого преимущества над итерационным.
Однако рекурсия функции лучше решает сложные, многоуровневые задачи. Метод рекурсии поможет выполнить их быстрее и понятнее, а еще, что немаловажно, решение задач методом рекурсии легче поддерживать.
Продолжим рассматривать наш пример из summa(n). Есть два требования, без выполнения которых наш алгоритм не будет работать:
Должно быть четкое условие, выполнив которое процесс остановится и не будет повторяться до бесконечности. То есть такое условие дает возможность функции завершить работу. В программировании это называется базовым случаем. В нашей ситуации функция будет вызывать себя, пока не найдет «коробку с ключом».
При этом чем больше функция сделает вызовов, тем больше будет глубина рекурсии.
Чтобы базовый случай вообще произошел, нужна рабочая передача измененных данных каждой новой функции. Например, первый вызов n=5, второй n=4, и т.д. И только когда n становится равным 1, завершится рекурсия.
Теперь мы обратим внимание непосредственно на программирование из Python.
Итак, есть «материнская» функция и «дочерняя». В тот момент, когда функция вызывает самое себя, действие «материнской» останавливается, а вместо этого начинается выполнение «дочерней».
Рассмотрим рекурсивную функцию на примере summa(5). В компьютере хранятся данные о функциях в виде блока, в котором в свою очередь установлены значения переменной n и выполняемый код. Наглядно это выглядит так:
При выполнении функции summa(5) начинает вызывать summa(4). В настоящее время формируется новый блок и размещается над предыдущим:
Так продолжается, пока работает рекурсия функции. При этом только начинает работать новый блок, остальные никак не введены в эксплуатацию и просто хранят имеющиеся данные.
И так продолжается до того момента, когда рекурсия достигает базового случая:
Далее summa(1) возвращает единицу, завершает работу и выходит из стека. В верхней части остается summa(2). Теперь summa(2) продолжает исполнение с того момента, на котором остановилась. За ней – summa (3) и так далее до завершения стека. Во время этого процесса мы можем заметить некоторую особенность рекурсии функции в программировании. Проблема в том, что в то время, когда рекурсивные функции выполняются, они сохраняют данные обо всех незавершенных функциях, вследствие чего повышается потребление памяти.
Здесь важно упомянуть особенности языка программирования Python, он имеет ограничение стека до 1 000 вызовов. То есть, когда количество звонков превышает лимит, вы получите сообщение об ошибке, а именно – "Переполнение стека". Важно помнить об этом ограничении, когда вы работаете в среде Python вообще, в частности с рекурсией функции.
Прочитав эту статью, вы можете задать себе один важный вопрос: "А вообще нужно ли пользоваться рекурсией функции в Python, если этот результат можно получить и с помощью итеративных алгоритмов?" Вопрос абсолютно логичный!
Есть ситуации, в которых итеративные циклы будут более эффективными. К тому же они также могут использовать рекурсивные структуры данных. Также рекурсивные функции занимают ощутимо больше памяти, потому что постоянно заполняют новыми слоями. Хотя рекурсивные функции обладают ощутимо более высокой эффективностью.
В общем, рекурсивные функции – это инструмент, на изучение и освоение которого нужно приложить некоторые силы. При неправильном использовании рекурсия невыгодна, ведь вычисления проводятся чаще, чем это действительно нужно. Чтобы избегать подобных ошибок, ознакомиться с рекурсивными функциями нужно из самых простых задач.
Главное преимущество рекурсивных функций над итеративными, это простота кода.
def factorial_iterative(num):
factorial = 1
if num < 0:
print("Factorial is not calculated for negative numbers")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f"Factorial {num} is {factorial}")
>>> import sys
>>> sys.getrecursionlimit()
3000
