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

1. Какие утверждения о рекурсии верны? A. Рекурсивная функция обязательно содержит цикл for или while. B. Рекурсивная функция вызывает саму себя — напрямую или через другие функции. C. В рекурсивной функции должно быть условие остановки (базовый случай). D. Любую рекурсивную функцию невозможно заменить итеративным (циклическим) алгоритмом.

2. Какие утверждения о видах рекурсии верны? A. При прямой рекурсии функция вызывает саму себя. B. При косвенной рекурсии функции вызывают друг друга по цепочке (например, A вызывает B, а B — A). C. Хвостовой рекурсией называют случай, когда рекурсивный вызов является последней выполняемой операцией функции. D. Рекурсивная функция не может вызывать никакие другие функции, кроме самой себя.

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

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

Какие утверждения верны? A. f(5) равно 120. B. f(3) равно 6. C. При вызове f(0) возникает бесконечная рекурсия. D. Функция вычисляет сумму чисел от 1 до n.

4. Дана функция (n — натуральное число):

def s(n):
    if n < 10:
        return n
    return n % 10 + s(n // 10)

Какие утверждения верны? A. s(1234) равно 10. B. s(7) равно 7. C. s(100) равно 1. D. s(n) возвращает количество цифр в записи числа n.

5. Числа Фибоначчи вычисляются рекурсивно: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) при n ≥ 2. Какие утверждения верны? A. F(6) равно 8. B. Такая рекурсивная функция многократно вычисляет одни и те же значения F(k). C. Время работы такой рекурсивной функции растёт примерно экспоненциально с увеличением n. D. Значения F(0) и F(1) — не базовые случаи, а рекурсивные вызовы.

Ответы

1. B, C
2. A, B, C
3. A, B
4. A, B, C
5. A, B, C