В данной статье мы рассмотрим работу рекурсивных функция в Python. И также мы разберем их преимущества и недостатки.
Итак, приступим к делу!
Что такое рекурсивные функции в Python
Согласно Оксфордскому словарю английского языка, рекурсия — это повторное применение рекурсивной процедуры или определения.
Видите ли вы рекурсию в самом этом определении? Они использовали слово «рекурсивный» для определения «рекурсии». Тут чувствуется какой-то скрытый смысл.
Как бы то ни было, если мы уж заговорили о рекурсии, возьмем тогда самый крутой пример.
Взгляните на логотип PyPy. Это реализация Python с Just-In-Time (динамическим) компилятором.
Змея, кусающая себя за хвост и кормящая себя, — это пример рекурсии, который мы хотели бы вам привести.
Возьмем более общий пример: когда наша тревога вызывает у нас еще большую тревогу, это тоже рекурсия.
В программировании рекурсия — это когда функция вызывает сама себя. Мы подробно рассмотрим в следующих разделах нашей статьи.
Пример рекурсивной функции Python
Мы знаем, что в Python одна функция может вызывать другую. Но когда она вызывает сама себя, обязательно должно быть базовое условие и оператор декремента. Это нужно чтобы избежать бесконечного цикла.
В качестве примера работы рекурсивной функции мы рассмотрим вычисление факториала числа. Это своего рода Hello Worlds для рекурсии.
Факториал числа n это n * (n - 1) * (n - 2) * ... * 2 * 1. Скажем 5! = 5 * 4 * 3 * 2 * 1 = 120.
Давайте теперь напишем для этого рекурсивную функцию. Но сначала сделаем это без рекурсии:
def factorial(n):
f=1
while n>0:
f*=n
n-=1
print(f)
factorial(4)
# Результат
# 24
factorial(4)
# Результат:
# 120
Теперь реализуем то же самое при помощи рекурсии. Это означает что функция factorial() будет вызывать функцию factorial(), то есть саму себя.
def factorial(n):
if n==1:
return 1
return n*factorial(n-1)
print(factorial(5))
# Результат:
# 120
print(factorial(4))
# Результат
# 24
Видите как все просто?
Как работает рекурсивная функция
Точнее сказать, мы сейчас объясним как работает рекурсивная функция в Python.
Наша функция factorial(n) принимает число n в качестве аргумента. Базовое условие для выхода из рекурсии определено как n == 1. В этом случае функция должна вернуть значение 1.
В противном случае она вернет n умноженное на factorial(n - 1). Это и есть рекурсивный вызов функции самой себя. Итак, это будет выглядеть следующим образом:
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 *2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 5 * 4 * 3 * 2
= 5 * 4 * 6
= 5 * 24
= 120
Таким образом, в качестве результата выполнения функции factorial(5) мы получаем 120.
Исключение RecursionError
Как мы видели, наш код работал отлично. Но теперь давайте попробуем передать -2 в качестве аргумента.
factorial(-2)
Результат:
Traceback (most recent call last):File “<pyshell#262>”, line 1, in <module> factorial(-2) File “<pyshell#259>”, line 4, in factorial return n*factorial(n-1) File “<pyshell#259>”, line 4, in factorial return n*factorial(n-1) File “<pyshell#259>”, line 4, in factorial return n*factorial(n-1) [The Previous line repeated 989 more times] File “<pyshell#259>”, line 2, in factorial if n==1: RecursionError: maximum recursion depth exceeded in comparison
Добавьте это в список исключений в нашем руководстве по ошибкам и исключениям Python.
Рекурсивная функция в Python – аргументы за и против
Преимущества использования рекурсивной функции в Python
- код рекурсивной функции имеет очень ясный и чистый вид;
- рекурсия упрощает кодирование, так как разбивает задачу на более мелкие;
- генерировать последовательности проще с помощью рекурсии, чем с помощью вложенной итерации;
Недостатки использования рекурсивной функции Python
А вот обратная сторона медали:
- хотя код и имеет весьма чистый вид, иногда его не так просто понять;
- рекурсивные вызовы могут быть проще, но они дороже с точки зрения ресурсов компьютера, времени выполнения и расходования памяти;
- и наконец, отладка рекурсивной функции это непростая работа;
Дополнительные примеры использования рекурсивной функции в Python
Для лучшего понимания давайте рассмотрим еще пару примеров работы рекурсивной функции.
Для начала, давайте определим функцию для вычисления суммы первых n натуральных чисел.
def sumofn(n):
if n==1:
return 1
return n+sumofn(n-1)
print(sumofn(16))
# Результат:
# 126
Здесь: sumofn(16)= 16+sumofn(15)
=16+15+sumofn(14)
…
=16+120
=136
И под конец давайте рассмотрим еще один пример. В нем мы будем сохранять n первых членов последовательности Фибоначчи при заданном n.
a,b,fib=0,1,[]
fib.append(a)
fib.append(b)
def fibonacci(n):
if n == 2:
return
global a,b
a, b = b, a + b
fib.append(b)
fibonacci(n - 1)
print(fib)
# Результат:
# [0, 1]
fibonacci(9)
print(fib)
# Результат:
# [0, 1, 1, 2, 3, 5, 8, 13, 21]
Здесь мы делаем следующее: во-первых, мы сохраняем значения 0 и 1 в переменных a и b. Также мы определяем пустой массив fib. Затем мы добавляем в него значения a и b.
И теперь мы определяем нашу рекурсивную функцию fibonacci(). Базовым условием рекурсии будет n == 2, так как мы уже добавили в список два числа. Когда n станет равно 2 работа функции прекратится при помощи оператора return.
Наша основная логика находится в строке a, b = b, a + b. Здесь мы передаем значение b в переменную a, одновременно складывая оба значения и сохраняя сумму в переменную b. Затем мы добавляем значение b в список fib, а затем вызываем функцию fibonacci с аргументом n - 1.
И наконец, мы вызвали функцию с аргументом 9 и получили список чисел Фибоначчи с 9 числами. Разве это не здорово?
Итак, на этом пока все про рекурсию в Python. Надеемся, что вам было интересно.
Вопросы по рекурсивным функциям из собеседований
- Что такое рекурсивная функция в Python?
- Что такое рекурсия? Объясните на конкретных примерах.
- Как работает рекурсивная функция в Python?
- Какая польза от рекурсивных функций в Python?
Заключение
В данной статье мы рассмотрели рекурсию в Python и примеры ее использования.
Мы разобрали преимущества и недостатки рекурсивных функций. Несмотря на то, что их использование дорого с точки зрения вычислительных ресурсов, они обеспечивают высокую чистоту кода.
Продолжайте упражняться в написании рекурсивного кода и решайте с его помощью задачи по программированию.
Перевод статьи Learn Python Recursion Function – Example, Pros and Cons.