Информатика · Пробное ЕНТ

Рекурсия: тест ЕНТ

Проверьте знания по теме «Рекурсия» для подготовки к ЕНТ. Формулы, логические выражения и математические обозначения отображаются через MathML.

20 вопросов4 варианта ответаПроверка сразуОбъясненияБез регистрации

Вопрос 1 из 20Правильных ответов: 0

✓

Тест завершён

Ваш результат по теме «Рекурсия»

0 / 20

Другие тесты по информатике

Подготовка к ЕНТ: Рекурсия

Тематический тест помогает проверить не весь курс, а конкретный раздел «Рекурсия». Такой формат удобен для повторения после урока, самостоятельной подготовки и поиска слабых мест.

Как работать с результатом

Не ограничивайтесь итоговым числом правильных ответов. Обратите внимание, какие понятия были перепутаны и почему выбранный вариант показался верным. После объяснения попробуйте своими словами сформулировать правило или алгоритм, логическое правило или вычислительную закономерность.

Повторное прохождение имеет смысл после короткого повторения темы. Цель — понимать связь между данными, алгоритмом, кодом и результатом выполнения, а не запоминать расположение ответов.

Базовый случай · Рекурсивный шаг · Стек вызовов · Возврат

Раскрывайте рекурсивные вызовы до базового случая, а затем вычисляйте результат в обратном порядке

Рекурсивная функция решает задачу через более простой экземпляр той же задачи. Для корректной работы нужен достижимый базовый случай. В заданиях ЕНТ важно уметь проследить аргументы вызовов, число уровней рекурсии и порядок возврата результатов.

01Найдите базовый случайЭто ветвь, которая возвращает результат без нового рекурсивного вызова.

02Проследите изменение аргументаОн должен приближаться к базовому случаю.

03Запишите цепочку вызововНапример f(4) → f(3) → f(2) → ....

04Возвращайтесь снизу вверхПосле базового случая результаты вычисляются в обратном порядке.

Ключевые понятия

РекурсияВызов функции самой себя напрямую или через цепочку других вызовов.

Базовый случайУсловие остановки дальнейшего углубления.

Рекурсивный шагПереход к более простому экземпляру задачи.

Стек вызововХранит состояние незавершённых вызовов функций.

ФакториалКлассический пример: n! = n·(n-1)! при подходящем базовом случае.

ВозвратКаждый завершившийся внутренний вызов передаёт значение предыдущему уровню.

def f(n):
    if n == 0:
        return 1
    return n * f(n - 1)

Не подставляйте результат внешнего вызова раньше, чем полностью вычислен внутренний рекурсивный вызов.

Что важно для заданий ЕНТ

Сумма цифрМожно отделять последнюю цифру через % 10 и уменьшать число через // 10.

Разворот строкиПервый или последний символ можно соединять с результатом рекурсии для оставшейся части.

Шаг n-2Не все рекурсивные функции уменьшают аргумент на единицу.

Два рекурсивных вызоваТребуют особенно аккуратной трассировки, потому что дерево вызовов ветвится.

Число вызововВключает исходный вызов и все созданные им рекурсивные вызовы.

Ошибка остановкиЕсли аргумент не приближается к базовому случаю, возможна бесконечная рекурсия до ошибки глубины.

f(4)
→ 4·f(3)
→ 4·3·f(2)
→ 4·3·2·f(1)
→ ...
→ возврат снизу вверх

Если функция вызывает себя дважды, одинаковые аргументы могут вычисляться повторно. В тестах важно считать именно фактические вызовы по данному коду.

Алгоритм

Как решать задания по теме «Рекурсия»

Найдите условие остановки

Что возвращается без рекурсии?

Проверьте движение аргумента

Уменьшается ли задача к базовому случаю?

Раскройте вызовы

Записывайте каждый новый аргумент.

Отметьте ветвление

Если рекурсивных вызовов два, стройте небольшое дерево.

Дойдите до базовых значений

Только после этого начинайте обратный расчёт.

Соберите результат

Выполняйте операции в порядке возврата из вызовов.

Частые ошибки

Что особенно важно не перепутать

Не находят базовый случай

Без него невозможно понять момент остановки.

Считают только один уровень

Рекурсивный вызов сам запускает ту же функцию.

Путают порядок возврата

Сначала завершается самый глубокий вызов.

Забывают второй вызов

В выражениях типа f(n-1)+f(n-2) обе ветви важны.

Считают число значений вместо числа вызовов

Повторный вызов с тем же аргументом всё равно является отдельным вызовом.

Игнорируют изменение строки или числа

Каждый уровень получает уже сокращённый аргумент.