В данной статье мы рассмотрим работу рекурсивных функция в 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.