Что такое рекурсия?
Простой пример рекурсии, из реального мира, это два зеркала, которые стоят друг напротив друга. Отражение любого объекта между двух зеркал и будет называться рекурсией.
В предыдущих примерах с функциями, мы уже знаем что одна функция может вызвать другую функцию. Функция так же может вызывать саму себя. Такие типы функций, называются рекурсивными функциями. Самый лучший метод разъяснения, это конечно же примеры. Ниже приведен пример функции с рекурсией, которая находит факториал числа.
Факториал — это произведение всех числа от 1 до конечного числа. К примеру, факториал цифры 6 (обозначение факториала 6!), 1*2*3*4*5*6 = 720.
Пример рекурсивной функции
def factorialnum(x):
"""Это рекурсивная функция, которая
находит факториал числа"""
if x == 1:
return 1
else:
return(x * factorialnum(x - 1))
number = 10
print("Факториал числа", number, "равно", factorialnum(number))
Результат:
Факториал числа 10, равен 3628800
В приведенном примере, мы видим, что функция factorialnum(), вызывает саму себя, поэтому она и является рекурсивной функцией. Логика работы этой функции заключается в том, что она каждый раз вызывает саму себя, уменьшая наше конечное число. То есть, функция вызывает саму себя, при этом умножает число на факториал, который ниже самого числа до тех пор, пока она не станет равным единице. Ниже приведен пример, пошагового разбора.
factorialnum(10) # 1ый вызов 10 10 * factorialnum(9) # 2ой вызов 9 10 * 9 * factorialnum(8) # 3ий вызов 8 10 * 9 * 8 # И так, до тех пор, пока не будет равно единице</pre> <pre>
На изображении ниже, приведен пример, на котором изображен процесс всего происходящего в самом коде.
Важно запомнить! При изучении цикла while, мы с вами обсуждали бесконечный цикл. Точно так же, при отсутствии условия, которая останавливает рекурсию, функция будет бесконечно вызывать саму себя. Если мне не изменяет память, то Python ограничивает глубину рекурсии по умолчанию до 1000, при пересечении этого предела, выйдет ошибка RecursionError.
Рассмотрим функцию с таким условием:
def recurs():
recurs()
recurs()
Результат:
RuntimeError: maximum recursion depth exceeded
Преимущества рекурсии
- Рекурсивная функция делает код чистым и красивым
- Сложная задача может быть разбита на более простые подзадачи с помощью рекурсии
- Генерация определенных последовательностей проще реализовать с помощью рекурсии
Недостаток рекурсии
- Довольно часто бывает такое, что понять логику рекурсии сложно, особенно если ее писали не вы
- Рекурсивные функции занимают много памяти и зачастую много времени
- Рекурсивные функции исходя из первого пункта сложнее отлаживать
