В каких случаях используется рекурсия

# Рекурсия: Когда и как использовать

Рекурсия — это когда функция вызывает саму себя. Это мощный инструмент, но его нужно использовать осторожно, так как он может привести к переполнению стека (stack overflow) или медленной работе.

Основная идея

Рекурсия работает когда задача можно разбить на меньшие идентичные задачи:

Задача: посчитать факториал 5
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1  <- базовый случай

Рекурсия всегда состоит из двух частей:

def recursive_function(n):
    # 1. Базовый случай (условие выхода)
    if n == 0:
        return 1  # Рекурсия должна где-то остановиться
    
    # 2. Рекурсивный случай (вызов самого себя с меньшей задачей)
    return n * recursive_function(n - 1)

Случаи, когда рекурсия уместна

1. Обход древовидных структур (САМЫЙ ЧАСТЫЙ СЛУЧАЙ)

Деревья и графы по своей природе рекурсивны. Это самый важный случай.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def traverse_tree(node: TreeNode):
    """Обход дерева в глубину (DFS)."""
    if node is None:
        return
    
    print(node.value)
    
    # Рекурсивно обходим всех потомков
    for child in node.children:
        traverse_tree(child)

# Использование
#       1
#      / \
#     2   3
#    /
#   4

root = TreeNode(1)
root.children.append(TreeNode(2))
root.children.append(TreeNode(3))
root.children[0].children.append(TreeNode(4))

traverse_tree(root)  # Выведет: 1, 2, 4, 3

Почему рекурсия здесь хороша:

• Структура дерева рекурсивна (каждое поддерево — это дерево)
• Код очень чистый и понятный
• Дерево обычно не очень глубокое

2. Поиск в файловой системе

import os
from pathlib import Path

def find_all_python_files(directory: Path):
    """Рекурсивно находит все .py файлы."""
    python_files = []
    
    for item in directory.iterdir():
        if item.is_file() and item.suffix == '.py':
            python_files.append(item)
        elif item.is_dir():
            # Рекурсивно ищем в подпапках
            python_files.extend(find_all_python_files(item))
    
    return python_files

# Использование
files = find_all_python_files(Path('.'))
for file in files:
    print(file)

3. Backtracking (возврат назад) — NP-полные задачи

Это задачи, где нужно перебрать много вариантов и найти решение.

Пример 1: N-Queens Problem

def solve_n_queens(n: int) -> list:
    """Решает задачу о восьми королевах."""
    solutions = []
    board = [-1] * n  # board[i] = столбец королевы в строке i
    
    def is_safe(row: int, col: int) -> bool:
        """Проверяет, можно ли поставить королеву на (row, col)."""
        for prev_row in range(row):
            prev_col = board[prev_row]
            # Проверяем: тот же столбец или диагональ
            if prev_col == col or abs(prev_row - row) == abs(prev_col - col):
                return False
        return True
    
    def backtrack(row: int):
        if row == n:
            # Нашли решение
            solutions.append(board[:])
            return
        
        # Пробуем поставить королеву в каждый столбец
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)  # Рекурсивно решаем для следующей строки
                board[row] = -1  # Откатываем (backtrack)
    
    backtrack(0)
    return solutions

# Результат: все возможные расстановки 8 королев
solutions = solve_n_queens(8)
print(f"Найдено {len(solutions)} решений")  # 92 решения

Пример 2: Поиск пути в лабиринте

def find_path_in_maze(maze: list[list[int]], start: tuple, end: tuple) -> bool:
    """Находит путь из start в end в лабиринте.
    0 = проход, 1 = стена
    """
    rows, cols = len(maze), len(maze[0])
    visited = set()
    
    def backtrack(row: int, col: int) -> bool:
        # Базовые случаи
        if (row, col) == end:
            return True  # Нашли конец
        
        if (row < 0 or row >= rows or col < 0 or col >= cols or
            maze[row][col] == 1 or (row, col) in visited):
            return False  # Вышли за границы, стена, или уже посетили
        
        visited.add((row, col))
        
        # Пробуем все 4 направления: вверх, вниз, влево, вправо
        if (backtrack(row - 1, col) or  # Вверх
            backtrack(row + 1, col) or  # Вниз
            backtrack(row, col - 1) or  # Влево
            backtrack(row, col + 1)):   # Вправо
            return True
        
        # Откатываем (не обязательно, но помогает отладке)
        visited.discard((row, col))
        return False
    
    return backtrack(start[0], start[1])

# Пример использования
maze = [
    [0, 1, 0, 0],
    [0, 1, 0, 1],
    [0, 0, 0, 0],
    [1, 1, 1, 0]
]

if find_path_in_maze(maze, (0, 0), (3, 3)):
    print("Путь найден")
else:
    print("Пути нет")

4. Разделяй и властвуй (Divide and Conquer)

Merge Sort

def merge_sort(arr: list) -> list:
    """Сортировка слиянием."""
    if len(arr) <= 1:
        return arr  # Базовый случай: один элемент — уже отсортирован
    
    # Разделяем
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # Объединяем
    return merge(left, right)

def merge(left: list, right: list) -> list:
    """Объединяет две отсортированные последовательности."""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Сложность: O(n log n)
arr = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

Binary Search

def binary_search(arr: list, target: int, left: int = 0, right: int = None) -> int:
    """Бинарный поиск в отсортированном массиве."""
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1  # Не найдено
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid  # Найдено
    elif arr[mid] < target:
        # Рекурсивно ищем в правой половине
        return binary_search(arr, target, mid + 1, right)
    else:
        # Рекурсивно ищем в левой половине
        return binary_search(arr, target, left, mid - 1)

# Сложность: O(log n)
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))  # 3

5. Динамическое программирование (обычно лучше чем рекурсия)

Рекурсия часто неэффективна для DP, но можно использовать с мемоизацией.

def fibonacci_recursive(n: int) -> int:
    """Рекурсивный Фибоначчи — МЕДЛЕННО! O(2^n)"""
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# fibonacci_recursive(40) — займет секунды

# Лучше: мемоизация
def fibonacci_memoized(n: int, memo: dict = None) -> int:
    """Рекурсивный Фибоначчи с мемоизацией — O(n)"""
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    return memo[n]

print(fibonacci_memoized(40))  # Мгновенно

# Еще лучше: итеративный DP
def fibonacci_iterative(n: int) -> int:
    """Итеративный Фибоначчи — O(n), без переполнения стека"""
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

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

1. Простые итерации

# Плохо — рекурсия
def sum_recursive(arr: list, index: int = 0) -> int:
    if index == len(arr):
        return 0
    return arr[index] + sum_recursive(arr, index + 1)

# Хорошо — итерация
def sum_iterative(arr: list) -> int:
    return sum(arr)  # Или:
    # total = 0
    # for num in arr:
    #     total += num
    # return total

2. Очень глубокие рекурсии (может быть stack overflow)

# Опасно: рекурсия на 10000 элементов
def process_large_list(items: list, index: int = 0):
    if index == len(items):
        return
    print(items[index])
    process_large_list(items, index + 1)  # RecursionError!

# Безопасно: используй цикл
def process_large_list_safe(items: list):
    for item in items:
        print(item)

3. Задачи, которые легче решить итеративно

# Сложная рекурсия
def print_all_permutations(items: list, current: list = None):
    if current is None:
        current = []
    
    if not items:
        print(current)
        return
    
    for i in range(len(items)):
        new_items = items[:i] + items[i+1:]
        print_all_permutations(new_items, current + [items[i]])

# Проще: используй itertools
from itertools import permutations
for perm in permutations([1, 2, 3]):
    print(perm)

Практические советы

1. Используй @lru_cache для мемоизации

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Автоматически кеширует результаты
print(fibonacci(100))  # Быстро

2. Установи лимит рекурсии

import sys

# По умолчанию ~1000
print(sys.getrecursionlimit())  # 1000

# Можно увеличить (но риск stack overflow)
sys.setrecursionlimit(10000)

3. Используй tail recursion оптимизацию вручную

# Python не оптимизирует tail recursion, но можно переписать
# Хвостовая рекурсия:
def factorial_tail(n: int, acc: int = 1) -> int:
    if n == 0:
        return acc
    return factorial_tail(n - 1, n * acc)  # Последний вызов

# Можно переписать в loop (хотя Python не оптимизирует автоматически)
def factorial_loop(n: int) -> int:
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

Ключевые выводы

1. Рекурсия отлично подходит для:

   • Обхода деревьев и графов
   • Backtracking и поиска решений
   • Divide and conquer алгоритмов
   • Работы с рекурсивными структурами

2. Всегда нужен базовый случай — иначе бесконечная рекурсия

3. Используй мемоизацию (@lru_cache) для DP задач

4. Избегай рекурсии для:

   • Простых итераций
   • Обработки больших данных (риск stack overflow)
   • Задач, которые проще решить итеративно

5. Stack overflow при глубокой рекурсии — переписывай итеративно