В этом руководстве вы научитесь создавать рекурсивную функцию (функцию, которая вызывает сама себя).
Что такое рекурсия?
Рекурсия - это процесс определения чего-либо в терминах самого себя.
В качестве примера физического мира можно поместить два параллельных зеркала, обращенных друг к другу. Любой объект между ними будет отражаться рекурсивно.
Рекурсивная функция Python
В Python мы знаем, что функция может вызывать другие функции. Функция даже может вызывать сама себя. Эти типы конструкций называются рекурсивными функциями.
На следующем изображении показана работа рекурсивной функции с именем recurse.
Рекурсивная функция в Python
Ниже приведен пример рекурсивной функции для поиска факториала целого числа.
Факториал числа - это произведение всех целых чисел от 1 до этого числа. Например, факториал числа 6 (обозначается как 6!) Равен 1 * 2 * 3 * 4 * 5 * 6 = 720.
Пример рекурсивной функции
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Вывод
Факториал 3 равен 6
В приведенном выше примере factorial()это рекурсивная функция, которая вызывает сама себя.
Когда мы вызываем эту функцию с положительным целым числом, она рекурсивно вызывает себя, уменьшая число.
Каждая функция умножает число на факториал числа под ним, пока оно не станет равным единице. Этот рекурсивный вызов можно объяснить следующими шагами.
factorial (3) # 1-й вызов с 3 3 * factorial (2) # 2-й вызов с 2 3 * 2 * factorial (1) # 3-й вызов с 1 3 * 2 * 1 # возврат из 3-го вызова как number = 1 3 * 2 # возврат из 2-го звонка 6 # возврат из 1-го звонка
Давайте посмотрим на изображение, которое показывает пошаговый процесс того, что происходит:
Работа рекурсивной факториальной функции
Наша рекурсия заканчивается, когда число уменьшается до 1. Это называется базовым условием.
Каждая рекурсивная функция должна иметь базовое условие, которое останавливает рекурсию, иначе функция вызывает себя бесконечно.
Интерпретатор Python ограничивает глубину рекурсии, чтобы избежать бесконечных рекурсий, приводящих к переполнению стека.
По умолчанию максимальная глубина рекурсии составляет 1000. Если предел превышен, результатом будет RecursionError. Давайте посмотрим на одно из таких условий.
def recursor(): recursor() recursor()
Вывод
Traceback (последний вызов последним): файл "", строка 3, в файле "", строка 2, в файле "", строка 2, в файле "", строка 2, в (Предыдущая строка повторяется еще 996 раз ) RecursionError: превышена максимальная глубина рекурсии
Преимущества рекурсии
- Рекурсивные функции делают код чистым и элегантным.
- Сложную задачу можно разбить на более простые подзадачи с помощью рекурсии.
- С помощью рекурсии создать последовательность проще, чем с использованием некоторой вложенной итерации.
Недостатки рекурсии
- Иногда трудно понять логику рекурсии.
- Рекурсивные вызовы дороги (неэффективны), так как занимают много памяти и времени.
- Рекурсивные функции сложно отлаживать.
