💻 Практические примеры

Пример 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. Сумма цифр числа

Берём последнюю цифру (n % 10) и рекурсивно суммируем оставшиеся (n // 10).

# 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. Переполнение стека

Бесконечная рекурсия без базового случая приводит к RecursionError. Для безопасности перехватим исключение.

# stack_overflow.py
import sys


def infinite():
    return infinite()


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

Как запустить в VS Code