Код на python рекурсия

Ниже приведены несколько примеров рекурсивных функций на Python с подробными пояснениями. Это подходит для общего среднего школьного уровня. Каждый пример содержит базовый случай (base case), рекурсивный случай и объяснение шагов работы. 1) Факториал Код: def factorial(n): if n < 0: raise ValueError("n должен быть неотрицательным") if n == 0 or n == 1: return 1 return n * factorial(n - 1) Пояснение по шагам: - Базовый случай: если n = 0 или n = 1, возвращаем 1. - Рекурсивный случай: для n > 1 возвращаем n умноженное на факториал от (n-1). - Например, factorial(4) = 4 * factorial(3) = 4 * (3 * factorial(2)) = 4 * 3 * (2 * factorial(1)) = 4 * 3 * 2 * 1 = 24. - Сложность: время O(n), память (глубина стека) O(n). 2) Сумма элементов списка (рекурсивно, без копирования подсписков) Вариант 1 (с срезами — проще, но копирует список): def sum_list_slice(lst): if not lst: return 0 return lst[0] + sum_list_slice(lst[1:]) Вариант 2 (эффективнее — без копирования): def sum_list(lst, idx=0): if idx >= len(lst): return 0 return lst[idx] + sum_list(lst, idx + 1) Пояснение: - Базовый случай: когда индекс достиг конца списка, возвращаем 0. - Рекурсивный случай: добавляем первый элемент и считаем сумму оставшегося списка. - Время: O(n), память: O(n) из-за глубины стека. 3) Рекурсия Фибоначчи (Naive) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) Пояснение: - Базовый случай: n = 0 или n = 1 возвращает n. - Рекурсивный случай: fib(n) = fib(n-1) + fib(n-2). - Проблема: экспоненциальное число вызовов, занятие времени очень велико для больших n (сложность примерно O(2^n)). - Советы: для практики можно добавить мемоизацию (ниже). Усовершенствованный вариант с мемоизацией: from functools import lru_cache @lru_cache(maxsize=None) def fib_m(n): if n <= 1: return n return fib_m(n - 1) + fib_m(n - 2) Пояснение: - Мемоизация сохраняет результаты уже посчитанных значений, значит каждый аргумент считается один раз. - Сложность времени: O(n), память: O(n) для хранения результатов. 4) Бинарный поиск рекурсивно def binary_search(arr, target, lo=0, hi=None): if hi is None: hi = len(arr) - 1 if lo > hi: return -1 # элемент не найден mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, hi) else: return binary_search(arr, target, lo, mid - 1) Пояснение: - Базовый случай: если диапазон пустой, элемент не найден. - Рекурсивный случай: ищем в половине, где может быть элемент. - Время: O(log n), память: O(log n) из-за глубины рекурсии. 5) Обход дерева (ин-order обход) Пример структуры узла дерева: class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right Ин-order обход: def inorder(node): if node is None: return [] return inorder(node.left) + [node.val] + inorder(node.right) Пояснение: - Базовый случай: если узел пустой, возвращаем пустой список. - Рекурсивный случай: сначала обходим левое поддерево, затем текущий узел, затем правое поддерево. - Время: O(n), где n — число узлов, память: O(h) для стека, где h — высота дерева. Полезные советы по рекурсии в Python: - Всегда определяйте явный базовый случай, чтобы остановить рекурсию. - Убедитесь, что размер входной задачи уменьшается на каждом шаге. - Избегайте лишних копирований данных в рекурсивном вызове (например, избегайте lst[1:] в больших списках; предпочитайте индекс или генераторы/итераторы). - В Python глубина рекурсии ограничена по умолчанию (обычно около 1000). Для очень глубоких рекурсий можно изменить лимит через sys.setrecursionlimit(), но это риск перегрузки стека и не рекомендуется без уважительной причины. - Для часто используемой повторной вычисляемой подзадачи используйте мемоизацию (lru_cache) или динамическое программирование (bottom-up). Если хочешь, могу подобрать задачку уровня твоего класса и разобрать её пошагово на основе конкретного предмета и класса.