"""
Урок 46. Рекурсия — весь код примеров одним файлом.

Источник: subjects/python-fundamentals/course/lessons/46-recursion/examples.html
Файл собран автоматически (tools/build_lesson_examples.py): правьте страницу урока.
Запуск: python lesson-46.py
"""



# ====================================================================
# Пример 1. Факториал
# ====================================================================
# factorial.py
def factorial(n: int) -> int:
    """Возвращает факториал неотрицательного целого числа."""
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))  # 120


# ====================================================================
# Пример 2. Бинарный поиск
# ====================================================================
# binary_search.py
from typing import Optional


def binary_search(
    arr: list[int],
    target: int,
    left: int,
    right: int
) -> Optional[int]:
    """Возвращает индекс target или None, если элемент не найден."""
    if left > right:
        return None
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    return binary_search(arr, target, left, mid - 1)


array = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(array, 5, 0, len(array) - 1))   # 2
print(binary_search(array, 13, 0, len(array) - 1))  # 6
print(binary_search(array, 8, 0, len(array) - 1))   # None


# ====================================================================
# Пример 3. Сумма цифр числа
# ====================================================================
# sum_digits.py
def sum_digits(n: int) -> int:
    """Рекурсивная сумма цифр числа."""
    n = abs(n)
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)


print(sum_digits(43197))  # 24


# ====================================================================
# Пример 4. Сумма чисел во вложенных списках
# ====================================================================
# sum_nested.py
from typing import Iterable


def sum_nested(data) -> int:
    """Суммирует все целые числа во вложенных итерируемых структурах."""
    if isinstance(data, int):
        return data
    if isinstance(data, Iterable) and not isinstance(data, (str, bytes)):
        return sum(sum_nested(item) for item in data)
    return 0


nested_numbers = [1, [2, 3], [4, [5, 6]], 7]
print(sum_nested(nested_numbers))  # 28


# ====================================================================
# Пример 5. Собственный аналог deepcopy
# ====================================================================
# custom_deepcopy.py
def deep_copy(data):
    """Рекурсивная копия вложенных коллекций."""
    if isinstance(data, list):
        return [deep_copy(item) for item in data]
    if isinstance(data, dict):
        return {key: deep_copy(value) for key, value in data.items()}
    if isinstance(data, set):
        return {deep_copy(item) for item in data}
    if isinstance(data, tuple):
        return tuple(deep_copy(item) for item in data)
    return data


original = [[1, 2], (4, [5, 6], {7, 8}), {"a": 9, "b": [10, 11]}]
copied = deep_copy(original)
original[1][1][0] = 0
print("Оригинал:", original)
print("Копия:   ", copied)


# ====================================================================
# Пример 6. Переворот строки
# ====================================================================
# reverse_string.py
def reverse_string(s: str) -> str:
    """Возвращает строку в обратном порядке."""
    if not s:
        return ""
    return s[-1] + reverse_string(s[:-1])


text = "hello"
print(reverse_string(text))  # olleh


# ====================================================================
# Пример 7. Подсчёт слова во вложенной структуре
# ====================================================================
# count_word.py
from typing import Iterable


def count_word(nested_sentences, word: str) -> int:
    """Считает вхождения слова во вложенных строках и списках."""
    if isinstance(nested_sentences, str):
        return nested_sentences.split().count(word)
    if isinstance(nested_sentences, Iterable) and not isinstance(nested_sentences, (str, bytes)):
        return sum(count_word(item, word) for item in nested_sentences)
    return 0


nested_sentences = [
    ["Python is great", "I love Python"],
    ["Python is powerful", ["Python is everywhere", "Learn Python"]],
    "Coding in Python is fun"
]
print("Количество вхождений:", count_word(nested_sentences, "Python"))  # 6


# ====================================================================
# Пример 8. Числа Фибоначчи: наивная и мемоизированная версии
# ====================================================================
# fibonacci.py
from functools import lru_cache


def fibonacci(n: int) -> int:
    """Наивная рекурсия (медленная для больших n)."""
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


@lru_cache(maxsize=None)
def fibonacci_fast(n: int) -> int:
    """Рекурсия с мемоизацией."""
    if n <= 1:
        return n
    return fibonacci_fast(n - 1) + fibonacci_fast(n - 2)


print(fibonacci(10))       # 55
print(fibonacci_fast(100))  # 354224848179261915075


# ====================================================================
# Пример 9. Переполнение стека
# ====================================================================
# stack_overflow.py
import sys


def infinite():
    return infinite()


print(f"Лимит рекурсии: {sys.getrecursionlimit()}")
try:
    infinite()
except RecursionError:
    print("Поймали RecursionError!")