🏋️ Раздел тренировки
Выполните задания в отдельных файлах. Начинайте с базового случая, затем добавляйте рекурсивный шаг. Для каждой функции добавьте docstring и аннотации типов.
Задание 1. Сумма цифр числа
Условие: напишите рекурсивную функцию sum_digits(n), которая возвращает сумму всех цифр числа.
Данные: num = 43197
Ожидаемый результат: 24
Подсказка: последняя цифра — n % 10, оставшаяся часть — n // 10.
Задание 2. Сумма вложенных чисел
Условие: напишите рекурсивную функцию sum_nested(numbers), которая суммирует все числа во вложенных списках.
Данные: nested_numbers = [1, [2, 3], [4, [5, 6]], 7]
Ожидаемый результат: 28
Подсказка: используйте isinstance(), чтобы отличить число от списка.
Задание 3. Факториал с проверкой
Условие: реализуйте factorial(n) с guard clause для отрицательных чисел и корректным базовым случаем.
Ожидаемый результат: factorial(5) == 120, factorial(0) == 1, factorial(-1) вызывает ValueError.
Задание 4. Бинарный поиск
Условие: напишите рекурсивную функцию binary_search(arr, target, left, right), которая возвращает индекс target или None.
Данные: array = [1, 3, 5, 7, 9, 11, 13]
Ожидаемый результат: поиск 5 → 2, 13 → 6, 8 → None.
Задание 5. Переворот строки
Условие: напишите рекурсивную функцию reverse_string(s), которая возвращает строку задом наперёд.
Данные: text = "hello"
Ожидаемый результат: "olleh"
Задание 6. Подсчёт слов
Условие: напишите рекурсивную функцию count_word(nested_sentences, word), которая считает вхождения слова во вложенных списках строк.
Данные:
nested_sentences = [
["Python is great", "I love Python"],
["Python is powerful", ["Python is everywhere", "Learn Python"]],
"Coding in Python is fun"
]
word = "Python"Ожидаемый результат: 6
Задание 7. Собственный аналог deepcopy
Условие: реализуйте функцию deep_copy(data), которая рекурсивно копирует списки, кортежи, множества и словари. Проверьте, что изменение копии не затрагивает оригинал.
Данные:
original_data = [
[1, 2, 3],
(4, [5, 6], {7, 8}),
{"a": 9, "b": [10, 11]},
"Hello",
[12, (13, 14)],
15.5,
5
]Проверка: после original_data[1][1][0] = 0 вложенный элемент в копии должен остаться неизменным.
Задание 8. Числа Фибоначчи с мемоизацией (★ дополнительно)
Условие: напишите рекурсивную функцию fibonacci(n) для вычисления n-го числа Фибоначчи. Ускорьте её с помощью functools.lru_cache.
Ожидаемый результат: fibonacci(10) == 55, fibonacci(100) работает быстро.