Приведи пример использования рекурсии

Рекурсия: примеры и применение

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

1. Факториал — классический пример

Факториал — это произведение всех чисел от 1 до N.

# Математическое определение:
# 0! = 1
# n! = n * (n-1)!

# Рекурсивная реализация:
def factorial(n: int) -> int:
    """Вычисли факториал n"""
    # Базовый случай (base case) — без него бесконечная рекурсия
    if n == 0:
        return 1
    
    # Рекурсивный случай (recursive case)
    return n * factorial(n - 1)

# Примеры:
print(factorial(0))   # 1
print(factorial(5))   # 120 (5*4*3*2*1)
print(factorial(10))  # 3628800

# Как это работает:
# factorial(5) = 5 * factorial(4)
#              = 5 * (4 * factorial(3))
#              = 5 * (4 * (3 * factorial(2)))
#              = 5 * (4 * (3 * (2 * factorial(1))))
#              = 5 * (4 * (3 * (2 * (1 * factorial(0)))))
#              = 5 * (4 * (3 * (2 * (1 * 1))))
#              = 120

2. Обход дерева файлов (практический пример)

import os
from pathlib import Path

def list_all_files(directory: str, indent: int = 0) -> None:
    """Рекурсивно вывести все файлы и папки"""
    try:
        items = os.listdir(directory)
    except PermissionError:
        return
    
    for item in items:
        path = os.path.join(directory, item)
        print(' ' * indent + item)
        
        # Рекурсивный вызов для папок
        if os.path.isdir(path):
            list_all_files(path, indent + 2)

# Использование:
list_all_files('/home/user')
# Выведет:
# Documents
#   report.pdf
#   spreadsheet.xlsx
# Downloads
#   image.jpg
#   archive.zip
# Pictures
#   vacation
#     photo1.jpg
#     photo2.jpg

3. Поиск в глубину (DFS) в графе

# Граф как словарь (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C', 'F'],
    'F': ['E']
}

def dfs(node: str, visited: set = None) -> list:
    """Поиск в глубину (Depth-First Search)"""
    if visited is None:
        visited = set()
    
    visited.add(node)
    result = [node]
    
    # Рекурсивно посещаем соседей
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            result.extend(dfs(neighbor, visited))
    
    return result

# Примеры:
print(dfs('A'))  # ['A', 'B', 'D', 'C', 'E', 'F']
print(dfs('E'))  # ['E', 'C', 'A', 'B', 'D', 'F']

4. Быстрая сортировка (QuickSort)

def quicksort(arr: list) -> list:
    """Быстрая сортировка через рекурсию"""
    # Базовый случай: массив из 0-1 элемента уже отсортирован
    if len(arr) <= 1:
        return arr
    
    # Выбираем pivot (опорный элемент)
    pivot = arr[len(arr) // 2]
    
    # Разделяем на три части: меньше, равно, больше
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    
    # Рекурсивно сортируем части и объединяем
    return quicksort(less) + equal + quicksort(greater)

# Примеры:
print(quicksort([5, 2, 8, 1, 9]))  # [1, 2, 5, 8, 9]
print(quicksort([3, 1, 4, 1, 5, 9]))  # [1, 1, 3, 4, 5, 9]

5. Вычисление расстояния между двумя точками (Levenshtein Distance)

def levenshtein_distance(s1: str, s2: str) -> int:
    """Минимальное число операций редактирования"""
    # Базовые случаи
    if len(s1) == 0:
        return len(s2)
    if len(s2) == 0:
        return len(s1)
    
    # Если первые символы совпадают, рекурсируем на остальное
    if s1[0] == s2[0]:
        return levenshtein_distance(s1[1:], s2[1:])
    
    # Если не совпадают, берём минимум из 3 операций:
    # 1. Удаление из s1
    # 2. Вставка в s1
    # 3. Замена символа
    return 1 + min(
        levenshtein_distance(s1[1:], s2),      # delete
        levenshtein_distance(s1, s2[1:]),      # insert
        levenshtein_distance(s1[1:], s2[1:])   # replace
    )

# Примеры:
print(levenshtein_distance('kitten', 'sitting'))  # 3
# kitten → sitten (замена k→s)
#        → sittin (замена e→i)
#        → sitting (вставка g)

print(levenshtein_distance('', 'abc'))  # 3 (вставить 3 символа)
print(levenshtein_distance('abc', 'abc'))  # 0 (они совпадают)

6. Поиск в упорядоченном массиве (бинарный поиск)

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, left, mid - 1)
    else:
        # Рекурсируем на правую половину
        return binary_search(arr, target, mid + 1, right)

# Примеры:
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 11))  # 5
print(binary_search(arr, 4))   # -1 (не найден)

Проблемы с рекурсией

Переполнение стека (Stack Overflow)

def bad_recursion(n):
    """Рекурсия без базового случая"""
    return bad_recursion(n + 1)  # Бесконечная рекурсия!

# Приведёт к:
# RecursionError: maximum recursion depth exceeded

Производительность: много повторных вычислений

# Плохо: экспоненциальная сложность O(2^n)
def fibonacci_slow(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)

# fibonacci_slow(5) вычисляет fibonacci_slow(4) дважды,
# fibonacci_slow(3) четыре раза и т.д.

# Хорошо: используем мемоизацию O(n)
def fibonacci_fast(n: int, cache: dict = None) -> int:
    if cache is None:
        cache = {}
    
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    result = fibonacci_fast(n - 1, cache) + fibonacci_fast(n - 2, cache)
    cache[n] = result
    return result

# Примеры:
print(fibonacci_slow(30))  # ~1 секунда (медленно)
print(fibonacci_fast(30))  # ~0.0001 секунды (быстро)

# Или использовать iterative подход:
def fibonacci_iterative(n: int) -> int:
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

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

✅ Хорошее применение:

1. Деревья и графы — дерево файловой системы, AST парсера, граф социальной сети
2. Разделение и conquering — QuickSort, MergeSort, двоичный поиск
3. Обход иерархических структур — JSON, XML, DOM
4. Задачи с естественной рекурсивной структурой — факториал, Фибоначчи, комбинаторика

❌ Плохое применение:

1. Простые итерации — используй for/while вместо рекурсии
2. Большие данные — risk переполнения стека
3. Критичная по производительности код — iterative часто быстрее

Лучшие практики рекурсии

def recursive_function(problem):
    """Правильно написанная рекурсивная функция"""
    
    # 1. Базовый случай (ОБЯЗАТЕЛЕН!)
    if is_base_case(problem):
        return base_case_solution
    
    # 2. Рекурсивный случай должен приближаться к базовому
    smaller_problem = reduce_problem(problem)
    
    # 3. Рекурсивный вызов
    return combine(recursive_function(smaller_problem), problem)

# Проверка:
# ✅ Есть базовый случай
# ✅ Проблема становится меньше с каждым вызовом
# ✅ Результаты правильно комбинируются

Вывод

Рекурсия — мощный инструмент для:

• Обхода деревьев и графов
• Алгоритмов разделения и conquering
• Решения задач с естественной рекурсивной структурой

Но нужно помнить:

• ✅ Всегда напиши базовый случай
• ✅ Каждый вызов должен приближаться к базовому
• ✅ Используй мемоизацию если есть повторные вычисления
• ✅ Для простых итераций лучше использовать loops
• ✅ Будь осторожен с переполнением стека на больших данных