Зачем это в ЕГЭ.
Задание 16 проверяет умение работать с рекурсивными функциями. Оно оценивается в 2 первичных балла и встречается практически в каждом варианте ЕГЭ. Задача требует анализа рекурсивного алгоритма и вычисления его результата.
Главная идея.
Рекурсивная функция вызывает сама себя, пока не достигнет базового случая (базы рекурсии). Ключ к решению — понять, как функция изменяет свои аргументы на каждом шаге, и отследить все вызовы до завершения.
Алгоритм (чеклист).
1. Определи, что делает функция: вычисляет значение, возвращает результат или изменяет данные.
2. Найди базовый случай (условие выхода из рекурсии).
3. Запиши последовательность вызовов функции, пока не достигнешь базового случая.
4. Вычисли результат, начиная с базового случая и двигаясь обратно.
5. Проверь, что все вызовы учтены и результат логичен.
Опоры (кратко).
- Базовый случай: условие, при котором рекурсия завершается.
- Рекуррентное соотношение: правило, по которому функция вызывает саму себя.
- Глубина рекурсии: количество вызовов до достижения базового случая.
Пример 1 (вычисление значения)
Дана функция:
pythondef f(n):
if n == 0:
return 1
return f(n - 1) + 2
Вычислите f(3).
*Шаг 1.* f(3) вызывает f(2) + 2.
*Шаг 2.* f(2) вызывает f(1) + 2.
*Шаг 3.* f(1) вызывает f(0) + 2.
*Шаг 4.* f(0) возвращает 1 (базовый случай).
*Шаг 5.* f(1) = 1 + 2 = 3.
*Шаг 6.* f(2) = 3 + 2 = 5.
*Шаг 7.* f(3) = 5 + 2 = 7.
Ответ: 7.
**Пример 2 (анализ вызовов)**
Дана функция: python
def f(n):
if n <= 1:
return n
return f(n - 1) + f(n - 2)
Сколько раз вызовется f(3)?
Шаг 1. f(3) вызывает f(2) и f(1).
Шаг 2. f(2) вызывает f(1) и f(0).
Шаг 3. f(1) возвращает 1 (базовый случай).
Шаг 4. f(0) возвращает 0 (базовый случай).
Шаг 5. f(2) = 1 + 0 = 1.
Шаг 6. f(1) возвращает 1 (базовый случай).
Шаг 7. f(3) = 1 + 1 = 2.
Ответ: 5 вызовов.
Типичные ошибки.
1. Неверное определение базового случая. Например, забыть проверить условие выхода из рекурсии.
2. Пропуск вызовов. Не учесть все рекурсивные вызовы функции.
3. Неправильный порядок вычислений. Начинать вычисления не с базового случая.
4. Путаница с аргументами. Неправильно передавать или изменять аргументы функции.
5. Зацикливание. Неправильное условие выхода из рекурсии приводит к бесконечному циклу.
Дальше.
Потренируйтесь на задачах с более сложными рекуррентными соотношениями и вложенными вызовами.