10 XP
ЕГЭ · Информатика · задание 162 балла · ≈10 мин

Задание 16 ЕГЭ: Рекурсия: вычисление значений рекурсивных функций

Дана рекурсивная функция: правило перехода и база. Нужно вычислить F(n) или посчитать, сколько чисел она выведет, — вручную, раскруткой от базы до нужного n, без запуска кода. Типичная потеря балла — ошибка в числе переходов: между F(1) и F(7) шесть шагов, а не семь.

Все задания Информатика

Что проверяет задание

Рекурсивные функции. Это задание с коротким ответом, который проверяется автоматически. Одна арифметическая ошибка — ноль баллов, поэтому скорость и аккуратность здесь важнее гениальности.

Формулы к заданию

Ветвящаяся рекурсия: значение через два предыдущих (числа Фибоначчи)
Факториал — классика линейной рекурсии
Линейная рекурсия с постоянным шагом d: от базы до n ровно n − 1 переходов

Разбор типовых задач

Пример 1

Функция задана правилом: F(1) = 1; F(n) = F(n-1) + 2 при n > 1. Чему равно F(8)?

Решение по шагам
  1. База: F(1) = 1. Дальше каждый шаг прибавляет двойку.
  2. От F(1) до F(8) семь переходов: 1 + 2 · 7.
  3. Проверка вручную: F(2)=3, F(3)=5, F(4)=7, F(5)=9, F(6)=11, F(7)=13, F(8)=15.

Ответ: 15

Пример 2

Функция задана правилом: F(1) = 1; F(n) = F(n-1) + n при n > 1. Чему равно F(6)?

Решение по шагам
  1. Раскручиваем сверху вниз: F(6) = F(5) + 6 = F(4) + 5 + 6 = … = F(1) + 2 + 3 + 4 + 5 + 6.
  2. F(1) = 1, складываем числа от 1 до 6.
  3. Тот же ответ проще получить столбиком: F(2)=3, F(3)=6, F(4)=10, F(5)=15, F(6)=21.

Ответ: 21

Пример 3

Программа записана псевдокодом: если n > 0, вывести n и вызвать F(n-2); иначе ничего не делать. Сколько чисел напечатает вызов F(11)?

Решение по шагам
  1. Первый вызов печатает 11 и передаёт управление F(9); тот печатает 9 и зовёт F(7).
  2. Цепочка значений: 11, 9, 7, 5, 3, 1. После 1 идёт вызов F(-1): условие n > 0 ложно — стоп.
  3. Печать стоит до рекурсивного вызова, поэтому считаем все элементы цепочки: их шесть.

Ответ: 6

Тренажёр задания (числа меняются)

Клавиши 1–9 выбирают вариант, Enter — «Проверить»

Функция задана правилом: F(1) = 1; F(n) = F(n-1) + 3 при n > 1. Чему равно F(7)?

Функция задана правилом: F(0) = 0; F(n) = F(n-1) + 2*n - 1 при n > 0. Чему равно F(6)?

Функция задана правилом: F(1) = 5; F(n) = F(n-1) + 2*n при n > 1. Чему равно F(9)?

Функция задана правилом: F(0) = 13; F(n) = F(n-1) - 1 при n > 0. Чему равно F(5)?

Что обязательно должно быть у рекурсивной функции, чтобы вычисление не зациклилось?

Рекурсивная функция обязана вызывать саму себя минимум дважды.

Функция задана правилом: F(1) = 1; F(n) = F(n-1) + 3 при n > 1. Чему равно F(11)?

Функция задана правилом: F(0) = 0; F(n) = F(n-1) + 2*n - 1 при n > 0. Чему равно F(10)?

Типичные ошибки

  • Путают число переходов: между F(1) и F(8) семь шагов правила, а не восемь.
  • Начинают раскрутку не с той базы: в условии база F(0), а решают от F(1) — ответ сдвигается.
  • В задаче «сколько чисел выведет» не замечают, стоит ли вывод до рекурсивного вызова или после него.
  • В ветвящейся рекурсии строят дерево хаотично и теряют вызовы: без таблицы значений F(n-2) считают дважды по-разному.

Повторить теорию по информатике

Разбор задания опирается на формулы и приёмы — если тема вспоминается с трудом, сначала пробегите уроки:

Формат задания 16 на экзамене

Балл за задание: 2. Ориентир по времени: ≈10 минут вместе с оформлением решения. Проверяемая тема: рекурсивные функции. На тренировке лимитов нет — сначала точность, скорость придёт после 10–15 решённых задач. Планируйте экзамен так, чтобы не застревать: если решение не идёт — зафиксируйте промежуточный результат, переходите дальше и возвращайтесь в конце, потому что остальные задания дадут больше суммарных баллов.

Частые вопросы про задание 16

Как вычислить F(n) в задании 16 ЕГЭ по информатике?

Раскрути рекурсию от базы вручную: выпиши F(1), F(2), F(3) и так далее до нужного n. Ошибки почти всегда в числе переходов, а не в арифметике.

Что такое базовый случай рекурсии?

Это значение функции, которое возвращается без вызова самой себя, например F(0) = 1. Именно с базы начинается раскрутка всех остальных значений.

Что делать, если рекурсия ветвящаяся, как F(n) = F(n-1) + F(n-2)?

Заполняй таблицу значений по порядку: F(1), F(2), F(3) и так далее до нужного номера. Каждое значение считай один раз и переиспользуй — дерево вызовов быстро разрастается.

Похожие задания