Рекурсия — это распространенная техника, которая часто ассоциируется с функциональным программированием. Основная идея заключается в следующем: если дана сложная задача, попробуйте найти процедуру, которая превращает исходную задачу в более простую версию той же задачи. Применяйте ту же процедуру несколько раз, чтобы делать задачу все проще и проще, пока не получите настолько простую задачу, что сможете решить ее за один подход.
Питонист может посмотреть на некоторые примеры рекурсии и подумать, что было бы проще написать цикл. Но в некоторых функциональных языках программирования циклов вообще нет, поэтому вам придется использовать рекурсию. Впрочем, в этих языках интерпретатор часто создает цикл за кулисами.
Тем не менее, существует множество задач, которые по своей природе являются рекурсивными. Их было бы очень трудно решить каким-либо другим способом, поэтому рекурсия обязательно должна быть в вашем арсенале.
Факториалы
Этот пример — небольшое клише, но он все равно хорошо иллюстрирует как красоту, так и подводные камни рекурсии.
Факториал целого числа n — это произведение всех целых чисел от 1 до n. Например, факториал 6 (обычно записывается как 6!):
6*5*4*3*2*1 = 720
Как мы уже говорили во введении, очевидный способ найти произведение всех чисел в ряду — использование цикла. Но есть и альтернативный, более «умный» способ — использование рекурсии.
Поразмыслив, мы понимаем, что 6! это фактически 6, умноженное на 5! А 5! — это 5, умноженное на 4!, и так далее. Таким образом, мы можем вычислить n!, не вычисляя факториал в явном виде. Мы просто продолжаем полагаться на все меньшие и меньшие факториалы, не вычисляя каждый из них.
Конечно, где-то нужно остановиться. Мы знаем, что 1! равен 1.
Вот код Python для вычисления факториала числа n. Мы возвращаем n раз факториал n — 1, если только n не равно 1 (тогда мы просто возвращаем 1):
def factorial(n):
if n>1:
x = n*factorial(n-1)
else:
x = 1
return x
print(factorial(6))
Удивительно, но это работает. Мы можем исследовать это дальше, добавив несколько отладочных операторов print:
def factorial(n):
print('Enter', n)
if n>1:
x = n*factorial(n-1)
else:
x = 1
print('Exit', n)
return x
Результат:
Enter 6 Enter 5 Enter 4 Enter 3 Enter 2 Enter 1 Exit 1 Exit 2 Exit 3 Exit 4 Exit 5 Exit 6
Как видите, мы вызвали функцию внутри функции внутри функции… Это определенно рекурсия.
Ограничения рекурсии
Рекурсия относительно неэффективна по сравнению с циклом. Это связано с тем, что каждый шаг в рекурсии приводит к вызову функции, тогда как каждый шаг в цикле просто требует «прыжка» в другое место кода.
Вызов функции требует значительно больше работы, чем простой цикл, и в любой системе он займет больше времени и будет использовать дополнительную память. Память требуется для хранения текущего состояния функции (значений ее локальных переменных) при каждом рекурсивном вызове функции.
Однако при программировании на Python вы столкнетесь и с другой, более важной проблемой. Рекурсивные вызовы ограничены глубиной в 1000. Приведенный выше код нельзя использовать для вычисления факториала любого числа больше 1000.
Это не означает, что рекурсия не является полезным инструментом в Python. Например, если вы обрабатываете двоичное дерево, глубина в 1000 позволяет обработать дерево, содержащее около 2¹⁰⁰⁰⁰ элементов. Это огромное число. Но если проблему можно решить с помощью простого цикла, это, вероятно, будет лучшим решением.
Хвостовая рекурсия
Форма рекурсии, которую демонстрирует факториал, называется хвостовой рекурсией. Хвостовая рекурсия — это когда рекурсивный вызов находится в самом конце функции (обычно с условием для завершения функции перед рекурсивным вызовом).
Если речь идет о хвостовой рекурсии, рекурсивный вызов функции обычно можно заменить циклом. В Python, как правило, так и следует делать!
Некоторые языки автоматически обнаруживают хвостовую рекурсию и заменяют ее циклом. Это часто называется TCO (Tail Call Optimisation). Python этого не делает. Как правило, это происходит в чистых функциональных языках, где циклов может не быть. Такие языки часто гораздо более декларативны, чем Python, что облегчает обнаружение хвостовой рекурсии.
Есть несколько хаков, позволяющих реализовать хвостовую рекурсию в Python, но здесь они не рассматриваются.
Неэффективная рекурсия — числа Фибоначчи
Вот еще один классический пример рекурсии — вычисление n-го числа Фибоначчи. Оказывается, использование чистой рекурсии для этого чудовищно не эффективно, но мы также рассмотрим полезный прием для облегчения этой задачи.
На случай, если вы не знакомы с последовательностью Фибоначчи: это бесконечный ряд чисел, определяемый следующим образом:
F0 = 0 F1 = 1 F2 = F1 + F0 = 1 F3 = F2 + F1 = 2 … F(n) = F(n-1) + F(n-2)
То есть каждый элемент последовательности является суммой двух предыдущих элементов.
Вот несколько первых значений последовательности Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21…
Очевидно, что n-й член последовательности можно вычислить рекурсивно, например так:
def fibonacci(n):
if n==0:
x = 0
elif n==1:
x = 1
else:
x = fibonacci(n-1) + fibonacci(n-2)
return x
print(fibonacci(8)) # 21
Обратите внимание, что нам нужно задать два начальных случая. F0 или F1 нельзя вычислить, они должны быть определены. Нумерация членов последовательности начинается с 0, поэтому 8-й элемент равен 21.
Давайте теперь посмотрим, как на самом деле работает эта функция. Для этого, как и раньше, добавим операторы print. Оказывается, это просто кошмар!
Вычисление F8 требует вычисления F7 и F6. Вот тут-то и начинается неэффективность, потому что, конечно, вычисление F7 также требует вычисления F6. Поскольку эти вычисления выполняются в отдельных ветвях рекурсии, F6 будет вычисляться дважды.
Вычисление F6 дважды требует, чтобы мы дважды вычислили F5, но мы также должны вычислить его снова как часть вычисления F7, поэтому в итоге мы вычисляем F5 три раза.
Вычисление F6 дважды и F5 трижды означает, что в итоге мы вычисляем F4 пять раз. Возможно, вы заметили закономерность: количество вычислений на каждом последующем более низком уровне рекурсии увеличивается в соответствии с последовательностью Фибоначчи!
Короче говоря, это ужасно неэффективный метод.
От редакции Pythonist: схему вызовов функции и еще один вариант объяснения можно найти в статье «Мемоизация, рекурсия и цикл for в Python».
Мемоизация
Основная проблема заключается в том, что мы вызываем fibonacci несколько раз, с одним и тем же аргументом, но каждый раз вычисляем значение заново.
Мы знаем, что fibonacci — это чистая функция. Она не имеет побочных эффектов, и каждый раз, когда вы вызываете ее с определенным значением, вы всегда получаете один и тот же результат.
Нам нужен какой-то способ запомнить все случаи ее вызова, сохранить результат и вычислять его только в том случае, если функция вызывается со значением, которое никогда не встречалось ранее. Мы можем сделать это с помощью словаря, в котором записаны все предыдущие вызовы. Ключ словаря — это аргумент функции, значение словаря — результат ее работы. Вот код:
cache = dict()
def fibonacci(n):
if n in cache:
return cache[n]
if n==0:
x = 0
elif n==1:
x = 1
else:
x = fibonacci(n-1) + fibonacci(n-2)
cache[n] = x
return x
print(fibonacci(8))
Здесь мы определяем пустой словарь под названием cache. Каждый раз, когда мы вводим функцию fibonacci, мы проверяем, существует ли значение n в словаре. Если да, то мы просто возвращаем предыдущее сохраненное значение для результата функции, которое находится в cache[n].
Если значения еще нет, мы вычисляем его обычным способом. Затем, перед возвратом fibonacci, мы сохраняем результат в cache, чтобы никогда не вычислять его снова.
lru_cache из functools
Все это хорошо, но это добавляет дополнительный код в функцию fibonacci. Лишний код мало связан с тем, что делает функция, он скорее касается повышения эффективности. А такое улучшение можно использовать и с другими функциями, не только с fibonacci.
Подобная сквозная функциональность — именно то, для чего были придуманы декораторы.
От редакции Pythonist. О декораторах читайте в статьях:
- Декораторы в Python: примеры использования
- Для чего нужны декораторы и как их использовать?
- Декораторы в Python: зачем они нужны и как их создавать
Другая проблема заключается в том, что наша реализация кэша довольно грубая и упрощенная. Она полагается на наличие глобальной переменной cache, которая бродит по файлу и надеется, что никто больше ее не использует. Эта реализация работает только для функций, принимающих ровно один аргумент. Также она позволяет кэшу расти до любого размера, хотя иногда разумнее было бы установить максимальный предел.
К счастью, существует декоратор lru_cache, который решает все эти проблемы. Он находится в модуле functools, и для его установки требуется всего одна строка кода:
from functools import lru_cache
@lru_cache()
def fibonacci(n):
print('Enter', n)
if n==0:
x = 0
elif n==1:
x = 1
else:
x = fibonacci(n-1) + fibonacci(n-2)
print('Exit', n)
return x
print(fibonacci(8))
Вот и все. Просто импортируйте декоратор, добавьте @lru_cache перед определением функции — и она будет вызывать fibonacci только один раз для каждого значения n.
Это значительно улучшит производительность кода для вычисления n-го элемента последовательности Фибоначчи, но не ожидайте такого же уровня улучшения для любого алгоритма. Для Фибоначчи это работает, потому что рекурсивный алгоритм изначально ужасно неэффективен.
Перевод статьи «Pros and cons of using recursion in Python».
