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

1. Какие утверждения о рекурсивной функции верны? Выберите все правильные варианты.

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

2. Что может произойти, если в рекурсивной функции нет условия остановки? Выберите все правильные варианты.

   • A. Рекурсивные вызовы могут привести к переполнению стека вызовов.
   • B. В Python слишком глубокая рекурсия обычно вызывает ошибку RecursionError.
   • C. Интерпретатор Python автоматически добавит базовый случай.
   • D. Любая такая функция обязательно вернёт None.

3. Дан код:

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

   Какие утверждения о вызове fact(4) верны? Выберите все правильные варианты.

   • A. Вызов fact(4) не завершится раньше, чем будет вычислено значение fact(3).
   • B. fact(4) возвращает 24.
   • C. При вычислении fact(4) функция fact вызывается 5 раз: с n = 4, 3, 2, 1, 0.
   • D. fact(4) возвращает 10, так как 4 + 3 + 2 + 1 = 10.

4. Какие утверждения о стеке вызовов при рекурсии верны? Выберите все правильные варианты.

   • A. Каждый незавершённый вызов функции хранится в стеке вызовов.
   • B. После возврата из рекурсивного вызова управление продолжается с места, следующего за этим вызовом.
   • C. Стек вызовов автоматически сортирует аргументы по возрастанию.
   • D. Рекурсивные вызовы не занимают память.

5. Дан код:

   def fib(n):
       if n <= 1:
           return n
       return fib(n - 1) + fib(n - 2)
   

   Какие утверждения о вычислении fib(5) верны? Выберите все правильные варианты.

   • A. fib(5) возвращает 5.
   • B. При вычислении fib(5) эта функция будет вызвана 15 раз, включая начальный вызов.
   • C. fib(5) возвращает 8.
   • D. При вычислении fib(5) значение fib(2) вычисляется только один раз.

6. Какие утверждения о сравнении рекурсии и итерации верны? Выберите все правильные варианты.

   • A. Любой алгоритм, записанный рекурсивно, можно реализовать итеративно, возможно, с явным стеком.
   • B. Рекурсивная реализация часто бывает короче и ближе к математическому определению задачи.
   • C. Рекурсия всегда работает быстрее итерации и занимает меньше памяти.
   • D. Итерация невозможна для задач, в которых есть повторяющиеся подзадачи.

7. Дан код:

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

   Какие утверждения о вызове f(3) верны? Выберите все правильные варианты.

   • A. f(3) возвращает 6.
   • B. При вычислении f(3) функция вызывается с n = 3, 2, 1, 0.
   • C. f(3) возвращает 3.
   • D. При вычислении f(3) функция вызывается с n = 3, 2, 1, 0, -1.

8. Дан код:

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

   Какие утверждения о вызове sum_digits(527) верны? Выберите все правильные варианты.

   • A. sum_digits(527) возвращает 14.
   • B. При вычислении sum_digits(527) происходят вызовы sum_digits(527), sum_digits(52) и sum_digits(5).
   • C. Базовый случай в этой функции — n < 10.
   • D. sum_digits(527) возвращает 527.

Ответы

1. A, B
2. A, B
3. A, B, C
4. A, B
5. A, B
6. A, B
7. A, B
8. A, B, C