🐍 Самоучитель по Python для начинающих. Часть 13: Рекурсивные функции
Расскажем, в каких случаях стоит использовать рекурсию, чем итеративный подход лучше рекурсивного и как можно ускорить выполнение рекурсивных функций в Python. В конце статьи решим 10 практических задач двумя способами – рекурсивным и итеративным.
Рекурсивная функция – это функция, которая вызывает сама
себя, и при каждом очередном вызове использует данные, созданные во время
предыдущего вызова. В программировании есть ряд задач, которые проще (но не
всегда эффективнее) решаются с помощью рекурсии. Написание рекурсивных
функций часто ставит начинающих программистов в тупик. Чтобы разобраться в
принципе работы рекурсивных функций, нужно понять (в самых общих чертах)
концепцию стекавызовов.
Стек –это структура
данных LIFO (lastin, firstout): информация
последовательно добавляется в «стопку» , каждый новый объект помещается поверх
предыдущего, а извлекаются объекты в обратном порядке, – начиная с верхнего.
Работу стека отлично иллюстрирует добавление данных в список с помощью append и извлечение
информации посредством pop:
Вывод:
Стек вызовов, в свою очередь, – это область памяти, в
которой выполняются функции. При каждом вызове функции создается фрейм –
фрагмент памяти, – в котором содержится:
информация о текущем состоянии выполнения функции;
значения всех переменных, которые функция получила для обработки;
локальные данные, созданные во время очередного вызова;
сведения о строке программы, к которой нужно вернуться после выполнения функции.
Фреймы помещаются в стек вызовов, как уже было показано в
примере выше, и удаляются точно так же, сверху вниз. Рекурсивные функции при
каждом новом вызове используют данные, созданные во время работы предыдущего
вызова.
Программисту не нужно беспокоиться о работе стека вызовов –
созданием фреймов и управлением стеком занимается интерпретатор. Однако
понимание принципа работы стека вызовов значительно упрощает создание
рекурсивных функций. Неверное же использование рекурсии приводит к переполнению
стека (stackoverflow).
Популярный сайт StackOverflow
назван как раз в честь этой ошибки.
Переполнить стек в опытных целях можно с помощью простейшей
рекурсивной функции, которая бесконечно вызывает сама себя, но не возвращает
никаких данных и не содержит никакого условия для прекращения своей работы:
Интерпретатор Python автоматически отслеживает переполнение стека и после 1000
бесплодных вызовов завершает работу подобных функций с ошибкой:
При желании лимит на глубину рекурсии можно увеличить, но
сделать его бесконечным, разумеется, нельзя – даже самый внушительный объем оперативной
памяти в итоге окажется переполненным:
Чтобы стек вызовов не переполнялся, в каждой рекурсивной
функции всегда должны быть предусмотрены два случая:
Граничный, при котором функция завершает работу и возвращает данные в основную программу.
Рекурсивный, при котором функция продолжает вызывать себя.
Вот пример простейшей рекурсивной функции, в которой учтены
оба случая:
Вызовы функции прекращаются, когда длина выводимой подстроки
достигает 0:
Эту же функцию можно переписать так, чтобы одно и то же условие проверяло и граничный, и рекурсивный случаи сразу:
И в первом, и во втором варианте рекурсивный случай
многократно передает в функцию greetings()
подстроку, длина которой уменьшается с каждым вызовом, пока не станет равной 0.
Скорость выполнения: итерация vs рекурсия
Рекурсивные функции работают медленнее обычных, поэтому их
стоит применять только тогда, когда решить задачу без рекурсии сложно. Вот
сравнение времени выполнения двух функций, рекурсивной fib_recursive(n)
и обычной fib_iter(n), решающих одну и ту же задачу –
вычисление последовательности Фибоначчи:
Результат для n = 15:
В приведенном выше примере в обычной функции используется
цикл for. Цикл
выполняет итерацию (перебор), причем справляется с задачей гораздо быстрее, чем
рекурсивная функция, поскольку рекурсия совершает множество повторных вызовов,
и с увеличением числа элементов последовательности количество повторов растет
лавинообразно:
Итерацию можно назвать противоположностью рекурсии. Всегда,
когда задачу можно решить итерацией (либо итерацией с использованием стека), следует
делать выбор в пользу циклаforили while
вместо рекурсии.
Мемоизация
Если применение рекурсии при решении задачи неизбежно, есть
простой способ ускорить выполнение функции – для этого используют декоратор
@lru_cache() модуля functools. Сравним скорость выполнения рекурсивного кода
при решении следующей олимпиадной задачи.
Задача: лесенка представляет собой набор кубиков. В этом наборе
каждый последующий ряд состоит из меньшего числа кубиков, чем предыдущий. Надо
написать программу для вычисления количества лесенок, которое можно построить
из nкубиков.
В решении используется рекурсивная функция, выполнение
которой в интерпретаторе Python
занимает столько времени, что готовое решение никогда не будет соответствовать
строгим олимпиадным критериям. Для кэширования промежуточных результатов можно
написать функцию мемоизации самостоятельно, а можно воспользоваться готовым,
уже упомянутым выше декоратором. Сравним скорость выполнения решений с
мемоизацией и без:
Результат теста:
Практика
Задание 1
Напишите функцию для вычисления факториала числа. Решите
задачу двумя способами – итеративным и рекурсивным.
Примечание для рекурсивного решения: предположим, нам нужно
вычислить 5! Факториал 5 равен: 5 х 4 х 3 х 2 х 1. Факториал 4: 4 х 3 х 2 х 1,
факториал 3: 3 х 2 х 1, факториал 2: 2 х 1, и факториал 1 равен 1. Очевидно,
что 5! = 5 x 4!, 4! = 4
x 3!, 3! = 3 x 2! и так далее до
граничного случая 1! = 1, то есть каждый последующий факториал включает в себя
определение предыдущего.
Пример ввода:
Вывод:
Решение 1 – итеративное:
Решение 2 – рекурсивное:
Задание 2
Напишите программу для возведения числа nв степень m. Решите задачу двумя
способами – итеративным и рекурсивным.
Примечание для рекурсивного решения: предположим, что нужно
возвести число 5 в степень 6. Свойства степени позволяют разбить процесс на
более мелкие операции и представить выражение 5 ** 6 в виде (5 ** 3) ** 2. Этот
подход работает в том случае, если степень представляет собой четное число.
Если степень нечетная, следует воспользоваться другим свойством: (n ** m) xn = n **
(m + 1). Поскольку
может ввести как четное, так и нечетное значение m, в функции должны быть два рекурсивных
случая. В качестве граничного случая используется еще одно свойство
степени:n ** 1 = n.
Пример ввода:
Вывод:
Решение 1 – итеративное:
Решение 2 – рекурсивное:
Задание 3
Напишите программу для нахожденияn-го гармонического числа.
Решите задачу итеративным и рекурсивным способами.
Пример ввода:
Вывод:
Решение 1 – итеративное:
Решение 2 – рекурсивное:
Задание 4
Напишите итеративную и рекурсивную функции для вычисления суммы
nпервых
членов геометрической прогрессии:
Пример ввода:
Вывод:
Решение 1 – итеративное:
Решение 2 – рекурсивное:
Примечание: если знаменатель не равен 1, задачу можно решить с помощью формулы суммы n первых членов геометрической прогрессии:
Задание 5
Напишите рекурсивную и итеративную функции для вычисления
наибольшего общего делителя чиселa и b.
Пример ввода:
Вывод:
Решение 1 – рекурсивное:
Решение 2 – итеративное:
Примечание: задачу можно решить с помощью math.gcd():
Задание 6
Напишите итеративную и рекурсивную функции для вычисления
последовательности n + (n – 2) + (n – 4)... (n – x =< 0), где n – натуральное четное число.
Пример ввода:
Вывод:
Решение 1 – итеративное:
Решение 2 – рекурсивное:
Задание 7
Напишите рекурсивную функцию, которая определяет, является
ли введенная пользователем строка палиндромом.
Пример ввода:
Вывод:
Решение:
Без рекурсии задачу можно решить так:
Задание 8
Напишите рекурсивную функцию для поиска имени,
состоящего ровно из 9 букв. Структура родословной, в которой хранятся данные об именах,
имеет древовидную форму:
Вывод:
Решение:
Примечание: без рекурсии такую задачу можно решить с помощью ООП:
Задание 9
Имеется многомерный вложенный список:
Напишите рекурсивную и итеративную функции для
преобразования списка в одномерный.
Ожидаемый результат:
Решение 1 – рекурсивное:
Решение 2 – итеративное:
Задание 10
Реализуйте алгоритм бинарного поиска с помощью итеративной и рекурсивной
функций. Число задается с помощью randrange(2000), в списке хранятся числа от 1
до 1000, т.е. не во всех случаях заданное число будет присутствовать в списке.
Пример вывода:
Решение 1 – рекурсивное:
Решение 2 – итеративное:
Подведем итоги
Рекурсию стоит применять для решения задач, в которых:
Используется древовидная структура данных.
Нужно предусмотреть возврат к предыдущей отправной точке (например, при поиске выхода из лабиринта).
Глубина рекурсивных вызовов находится в пределах разумного и не приведет к переполнению стека.
Во всех остальных случаях целесообразнее использовать итерацию либо итерацию и стек.
В следующей главе будем изучать функции высшего порядка и замыкания.
Комментарии