Тест по предмету «Информатика» на тему «Рекурсия»

1. Что называют рекурсией в программировании?

   A. Функция вызывает другую функцию и не возвращает значение
   B. Функция вызывает саму себя напрямую или через другие функции
   C. Программа выполняет один и тот же блок в цикле
   D. Функция принимает более одного аргумента

2. Что такое базовый случай в рекурсивной функции?

   A. Условие, при котором функция завершает вычисления без нового рекурсивного вызова
   B. Первый вызов функции из основной программы
   C. Максимальное число параметров функции
   D. Любой оператор return внутри функции

3. Что произойдёт, если в рекурсивной функции отсутствует условие остановки?

   A. Функция автоматически заменится циклом
   B. Программа не скомпилируется при любых условиях
   C. Вызовы будут продолжаться, пока не возникнет переполнение стека или ошибка глубины рекурсии
   D. Функция всегда вернёт 0

4. Какая запись правильно задаёт рекуррентную формулу факториала для \(n > 0\)?

   A. \(F(n) = n \cdot F(n-1), \quad F(0)=1\)
   B. \(F(n) = n + F(n-1), \quad F(0)=1\)
   C. \(F(n) = F(n-1)/n, \quad F(0)=1\)
   D. \(F(n) = (n-1)\cdot F(n), \quad F(0)=1\)

5. Дана функция:

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

   Чему равно fact(4)?

   A. 4
   B. 10
   C. 24
   D. 120

6. Дана функция: fib(n) = n при n < 2, иначе fib(n) = fib(n-1) + fib(n-2). Чему равно fib(6)?

   A. 5
   B. 6
   C. 8
   D. 13

7. Где во время выполнения рекурсивных вызовов обычно хранятся локальные переменные и адреса возврата активных вызовов?

   A. В стеке вызовов
   B. В куче
   C. В таблице базы данных
   D. В текстовом файле

8. В Python функция def f(n): return f(n + 1) вызывается как f(0). Какая ошибка обычно возникнет?

   A. ValueError
   B. RecursionError
   C. SyntaxError
   D. TypeError

9. Почему наивная рекурсивная реализация fib(n) = fib(n-1) + fib(n-2) без мемоизации может работать медленно при больших n?

   A. Она не использует параметры
   B. Она многократно вычисляет одни и те же значения
   C. Она всегда содержит бесконечный цикл
   D. Она не может вернуть число

10. Что такое мемоизация в рекурсивных вычислениях?

A. Увеличение максимальной глубины рекурсии
B. Удаление базового случая
C. Сохранение ранее вычисленных результатов для повторного использования
D. Замена всех операторов return на print

Ответы

1 — B
2 — A
3 — C
4 — A
5 — C
6 — C
7 — A
8 — B
9 — B
10 — C