Рекурсия

Рекурсия — это процесс, при котором функция вызывает саму себя.
В программировании рекурсия используется для решения задач, которые можно разбить на более простые подзадачи того же типа. Рекурсивные функции особенно полезны для работы с такими структурами данных, как деревья, графы, а также для решения задач, связанных с перебором или разделением (например, сортировка, поиск, вычисление факториала и т.д.).

Примеры рекурсии

Представим, что у нас есть автомат для продажи кофе. Клиент даёт автомату купюру, автомат готовит кофе и выдаёт сдачу. Сдача выдаётся монетами: 1, 2, 5 или 10 рублей.
Реализуем функцию которая выдаёт сдачу пользователя исходя из остатка денег после продажи кофе.
Принимаем кол-во монет бесконечным.

Задача: реализовать функцию, которая принимает в качестве параметра сумму, которую необходимо отдать пользователю в виде чисел (монет) 1, 2, 5, 10.

Решение:
def getChange(sum): coin = 0 if sum >= 10: # Если остаток больше или равен 10 coin = 10 elif sum >= 5: # Если остаток больше или равен 5 coin = 5 elif sum >= 2: # Если остаток больше или равен 2 coin = 2 elif sum >= 1: # Если остаток больше или равен 1 coin = 1 if coin > 0: # Если номинал монеты больше 0 print(coin) # Выдаём число (монету) # Вызываем функцию ещё раз уменьшая остаток, на выданное число getChange(sum - coin) getChange(37) # 10 10 10 5 2

В данном примере, на 15 строке вызывается функция getChange(), вызывется она внутри функции getChange(), получается, что функция вызывает сама себя - это и есть рекурсия!

Ещё пример задачи, где рекурсия применяется наиболее естественно, – это чтение содержимого каталога (директории), включая все вложенные подкаталоги.
Это реальная задача, решаемая при разработке облачного хранилища файлов.

Решение:
import os def read_directory_contents(path): # Получаем список всех файлов и директорий внутри текущего каталога items = os.listdir(path) for item in items: full_path = os.path.join(path, item) # Путь к текущему элементу if os.path.isdir(full_path): # Если это директория, вызываем функцию рекурсивно print(f"Каталог: {full_path}") read_directory_contents(full_path) # Рекурсивный вызов else: print(f"Файл: {full_path}") # Если это файл, просто выводим его путь # Вызов функции для чтения списка файлов из папки /path read_directory_contents("/path")

Показанная в примере функция вызывает сама себя на строке 12 - это и есть рекурсия!

Рассмотрим несколько классических арифметических примеров, где уместно использовать рекурсию.

Задача: реализовать функцию, для вычисления факториала числа n

Факториал числа n (обозначается n!) — это произведение всех положительных целых чисел от 1 до n.

Например: 5! = 5×4×3×2×1=120

Решение:
def factorial(n): # Базовый случай: факториал 0 или 1 равен 1 if n == 0 or n == 1: return 1 # Рекурсивный случай: n! = n * (n-1)! else: return n * factorial(n - 1) print(factorial(5)) # Вывод: 120

Глубина рекурсии

Рекурсия ограничена глубиной стека вызовов. По умолчанию в Python максимальная глубина рекурсии — около 1000. Это можно изменить с помощью sys.setrecursionlimit.

Пример:
import sys sys.setrecursionlimit(5) def recursion(n, counter=1): print(f"Вызов: {counter} из {n}") if (counter <= n): counter += 1 recursion(n, counter) recursion(6) # Вызовет переполнение стека

Преимущества рекурсии

  • Простота и читаемость: Рекурсивные решения часто более понятны и лаконичны, особенно для задач, которые естественно рекурсивны (например, обход деревьев).
  • Естественность для некоторых задач: Например, задачи, связанные с деревьями, графами, комбинаторикой.

Недостатки рекурсии

  • Переполнение стека: Глубокая рекурсия может привести к ошибке RecursionError.
  • Неэффективность: Рекурсивные вызовы могут быть медленными из-за накладных расходов на вызов функции.
  • Сложность отладки: Рекурсивные функции могут быть сложнее для отладки, особенно если глубина рекурсии большая.

Когда использовать рекурсию?

  • Задачи с естественной рекурсивной структурой: Например, обход деревьев, графов, задачи "разделяй и властвуй".
  • Когда важна читаемость кода: Рекурсия часто делает код более понятным.
  • Когда глубина рекурсии невелика: Для задач, где глубина рекурсии не превышает допустимых пределов.

Альтернатива рекурсии: Итерация

Многие рекурсивные задачи можно решить с помощью итерации (циклов). Итеративные решения обычно более эффективны по памяти и времени.

Пример итеративного вычисления факториала:
def factorial_iterative(n): result = 1 for i in range(1, n + 1): result *= i return result print(factorial_iterative(5)) # Вывод: 120

Рекурсия — мощный инструмент, но её нужно использовать с осторожностью, учитывая ограничения по глубине и производительности. Для задач с большой глубиной рекурсии лучше использовать итеративные решения.

Декораторы
Списки

Комментарии

Добавить комментарий

Чтобы оставить комменатрий необходимо Авторизоваться

Содежание
1. История создания Python 2. Установка интерпретатора Python и IDE 3. Hello world 4. Переменные и типы данных 5. Операторы 6. Взаимодействие с пользователем 7. Условные конструкции 8. Циклы 9. Списки и строки 10. Функции 11. Декораторы 12. Рекурсия 13. Списки 14. Словари 15. Кортежи 16. Множества 17. Основы ООП 18. Конструкторы и деструкторы 19. Наследование 20. Полиморфизм 21. Инкапсуляция 22. Методы работы со строками 23. Форматирование строк 24. Регулярные выражения 25. Пакетный менеджер pip 26. Обработка ошибок и исключений 27. Генераторы и итераторы 28. Асинхронное программирование 29. Многопоточность 30. Многопроцессорность