В этом уроке мы погрузимся в одну из самых интересных и мощных концепций программирования — рекурсию. Вы узнаете, как решать сложные задачи, разбивая их на более простые подзадачи. Мы разберем структуру рекурсивной функции, понятие базового случая (чтобы избежать бесконечного зацикливания) и рекурсивного шага.
Вы научитесь:
1. Определять базовые и рекурсивные случаи.
2. Читать и трассировать рекурсивный код.
3. Находить ошибки, приводящие к ошибке переполнения стека (RecursionError).
4. Реализовывать классические алгоритмы (факториал, числа Фибоначчи).
Будьте внимательны: в Python существует ограничение на глубину рекурсии, поэтому правильный выход из функции критически важен!
- Модуль 1: Основы синтаксиса Python
- Модуль 2: Переменные и типы данных
- Модуль 3: Операторы
- Арифметические операторы (+, -, *, /).
- Целочисленное деление и остаток (// и %).
- Возведение в степень (**).
- Операторы сравнения.
- Логические операторы (and, or, not).
- Операторы присваивания (=, +=, -=).
- Операторы принадлежности (in, not in).
- Операторы идентичности (is, is not).
- Битовые операторы.
- Тернарный оператор.
- Модуль 4: Ввод и вывод данных
- Модуль 5: Условные конструкции
- Модуль 6: Циклы
- Модуль 7: Строки
- Модуль 8: Списки
- Модуль 9: Кортежи
- Модуль 10: Словари
- Модуль 11: Множества
- Модуль 12: Функции
- Модуль 13: Встроенные функции
- Модуль 14: Работа с файлами
- Модуль 15: Обработка исключений
- Модуль 16: Модули и пакеты
- Модуль 17: ООП - Основы
- Модуль 18: ООП - Продвинутый уровень
- Модуль 19: Декораторы
- Модуль 20: Генераторы и итераторы
- Модуль 21: Регулярные выражения
- Модуль 22: Дата и время
- Модуль 23: Математические операции
- Модуль 24: Работа с сетью
- Модуль 25: Асинхронное программирование
- Модуль 26: Многопоточность
- Модуль 27: Тестирование
- Модуль 28: Базы данных
- Модуль 29: Алгоритмы и структуры данных
- Модуль 30: Продвинутые возможности
Основные понятия рекурсии
Чтобы правильно писать рекурсивные функции, нужно четко понимать их составные части. Сопоставьте термины с их определениями.
Обратный отсчет
Проанализируйте код функции обратного отсчета. Какой будет результат выполнения при вызове с аргументом 3? Обратите внимание на порядок оператора print и рекурсивного вызова.
def countdown(n):
if n <= 0:
print("Start!")
else:
print(n)
countdown(n - 1)
countdown(3)Сумма чисел от 1 до N
Допишите рекурсивную функцию, которая вычисляет сумму всех целых чисел от 1 до n. Вам нужно правильно написать условие базового случая и рекурсивный вызов.
def recursive_sum(n):
if n == 1:
return input1S
return n + input2SБесконечная рекурсия
В этой функции допущена критическая логическая ошибка, приводящая к `RecursionError`. Найдите строку, которая делает рекурсию бесконечной, и исправьте её. Цель функции — печатать числа от n до 0.
def print_numbers(n): if n == 0: return print(n) print_numbers(n)Рекурсивное возведение в степень
Соберите функцию `power(x, n)`, которая вычисляет $x^n$. Расставьте строки кода в правильном порядке: сначала проверка базового случая, затем рекурсивный шаг.
def power(x, n): return x * power(x, n - 1) if n == 0: return 1Факториал числа
Соберите функцию вычисления факториала ($n! = n \cdot (n-1)!$). Помните, что факториал 0 или 1 равен 1. Будьте внимательны, одна строка содержит ошибку и является лишней.
def factorial(n): if n <= 1: return 1 return n * factorial(n - 1) return n * factorial(n)Числа Фибоначчи
Заполните пропуски в функции для вычисления n-го числа Фибоначчи. В этой последовательности каждое следующее число — это сумма двух предыдущих. Базовые случаи: для n=1 и n=2 результат равен 1.
def fib(n):
if input1S <= 2:
return input2S
return fib(input3S) + fib(n - 2)Итерация против Рекурсии
Распределите утверждения между двумя подходами к решению задач: итеративным (циклы) и рекурсивным (вызов функции).
Что вернет функция?
Дана необычная рекурсивная функция. Вычислите в уме или на бумаге, что она вернет при вызове `mystery(10, 2)`. Введите только число.
def mystery(a, b):
if a < b:
return 0
else:
return 1 + mystery(a - b, b)
# mystery(10, 2)Ошибка выхода из рекурсии
Что произойдет при запуске этого кода? Внимательно посмотрите на условие в `if` и аргумент вызова.
def walk(n):
if n == 0:
return "Done"
else:
print(n)
return walk(n + 1)
walk(5)