Рекурсия в Python
Каждая программа должна выполнять какое-то действие и возвращать результат. А что, если для достижения необходимого результата нужно повторить одно и тоже действие множество раз. Как, используя язык программирования python, заставить компьютер повторить определенный алгоритм действий? Решение есть – рекурсия.
Рекурсия – это функция, которая вызывает саму себя определенное количество раз. В чем-то рекурсия похожа на циклы, но в ней есть ряд отличий. После каждой итерации, в рекурсивной функции могут измениться аргументы или же сама функция может прерваться с определенным результатом. Может ли такое сделать цикл? С большим трудом. К тому же рекурсия производится в отдельной функции, а не в теле основного кода, что делает программу более структурированной.
Аргументы функции в Python
Вот пример рекурсивной функции для нахождения факториала:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n — 1) # 5 * 4 * 3 * 2 * 1 = 120
print(factorial(5)) # 120
Что же в этой функции отвечает за рекурсивность? Обратите внимание на пятую строку. Операция return снова вызывает активную функцию, но уже с другим аргументом. Это происходит до тех пор, пока n не будет равно 0. После срабатывает условие n == 0, которое выводит программу из функции.
Зачем здесь вообще нужны условия, если достаточно просто прописать return n * factorial(n — 1). Условия выполняют роль переключателя для завершения функции. Если их не будет, то функция застрянет в бесконечном цикле, и программа выдаст ошибку рекурсии.
Резюме: аргументы в рекурсии постоянно меняются. Они указываются как в теле основного кода, так и в операции return.
Когда использовать рекурсию
В интернете часто возникают споры на тему выбора между рекурсией и циклом. В любом случае, оба варианта подходят если вам необходимо выполнить определенный кусок кода несколько раз. Однако у рекурсии есть ряд преимуществ:
- В python невозможно зациклить программу через рекурсивную функцию. Произойдет переполнение стека, а программа выдаст ошибку. Далее мы рассмотрим, как обойти эту ошибку.
- Рекурсивная функция более гибкая. С помощью условий и аргументов можно настроить ее на свой лад.
- В некоторых случаях рекурсия быстрее цикла.
- Рекурсия – это функция, а потому может вызываться множество раз.
Это лишь неполный список преимуществ рекурсии. Ниже представлены примеры задач, которые можно решить с помощью рекурсии:
- Вывод чисел в определенной последовательности
- Поиск факториала
- Методы сортировки
- Сумма всех цифр
- Проверка простого числа
- Поиск множителей
На самом деле потенциал рекурсии намного выше, а выше были предложены простые задачи для практики.
Увеличение максимальной глубины рекурсии
Python очень продуманный язык. Он не позволит «случайно» зациклить рекурсивную функцию. Зачем? Во-первых, зацикленная функция бесконечна. Программа даже не закроется. Она просто зависнет. Во-вторых, рекурсия выходит за пределы стека, а это одна из уязвимостей, которыми злоупотребляют хакеры.
Но порой расширить границы глубины рекурсии все же нужно. Например, когда результат функции выходит за пределы стека. Для реализации нам понадобится указать следующий фрагмент кода:
import sys
sys.getrecursionlimit() # узнать ограничения глубины рекурсии
sys.setrecursionlimit(n) # изменить ограничения на значение n
Но не стоит злоупотреблять данным методом, иначе это может привести к неоптимизированной работе программы.
Исследование дерева с рекурсией
Ниже показано представление рекурсивной функции поиска факториала.
Начинать читать лучше снизу. Изначально возвращаемый результат (далее ‘n’) равен 1, но после выполняется еще одна итерация, в которой n умножается на следующее, в порядке возрастания, число. Так происходит до тех пор, пока мы не доходим до аргумента 5. Возможно, сейчас вам трудно дается этот материал. Однако, такие деревья позволяют вручную проанализировать ход программы, чтобы выявить ошибку.
Рецепт создания функции в Python
Функция в python создается один раз, а вызываться может бесконечно много. Ключевое слово def сообщает интерпретатору, что дальше пойдет название функции и сама функция. Пример вызова:
deffuncName (args1, args2, args3):
#some code
return result
answer = funcName (args1, args2, args3)
Однако, бывают случаи, когда неизвестно сколько аргументов будет передано функцию. В данном случае необходимо перед последним аргументов указать символ *.
deffuncName (args1, args2, *args3)
Тогда все последующие элементы будут передаваться в список с названием третьего аргумента. Если некоторые обязательные аргументы не всегда передаются в функцию, то для них можно сделать значение по умолчанию
Пример:
def Person (name, city = “New-York”):
print(“Hi,”, name, “you are from”, city)
Person(“Jake”, “London”) # Hi, Jake you are from London
Person(“Mia”) # Hi, Mia you are from New-York
С рекурсивными функциями все тоже самое. Добавляется только повторный вызов функции в return. Главное, не забывайте добавлять условие, при выполнении которого программа выйдет из функции.
Как и когда происходит рекурсия
Мы разобрали рекурсию с точки зрения программиста. Но как же это происходит в самом интерпретаторе python? Когда мы работаем с функцией, мы выделяем для нее отдельное место в памяти. Адрес функции в памяти помещается в специальный буфер, который называется стек. Если нужно описать стек, то можно представить стакан.
Вы наливаете в него воду, которая слоем ложится на самый низ. После вы добавляете немного плотного масла, которое ложится поверх воды. Так происходит несколько раз и в итоге у вас есть стакан с разными слоями. Чтобы вылить из него воду, вам понадобится вылить верхний слой, потом следующий. Так до тех пор, пока вы не доберетесь до воды. В стеке все точно также. Самая первая функция находится в самом низу и завершается самой последней, а самая крайняя функция завершается первой.
Переполнение стека – это процесс, когда стакан заканчивается и жидкость выливается за пределы стенок. Это опасно как для самой программы, так и для данных пользователя. Надеемся, что данная статья помогла вам в изучении программирования!
