⚙️ Алгоритмы  ·  20 вопросов  ·  ~40 мин  ·  ⏱ Таймер 40:00  ·  Средний  · 

Рекурсия

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

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Что произойдёт при вызове f(3)?
Python
def f(n):
    if n == 0:
        return 0
    return n + f(n - 2)

print(f(3))
Вопрос 2 из 20
Какое значение вернёт функция?
Python
def digits(n):
    if n < 10:
        return 1
    return 1 + digits(n // 10)

print(digits(50700))
Вопрос 3 из 20
Какое свойство рекурсивного шага позволяет доказать завершение?
Вопрос 4 из 20
Как исправить функцию суммы списка, чтобы она работала и для пустого списка?
Python
def total(a):
    if len(a) == 1:
        return a[0]
    return a[0] + total(a[1:])
Вопрос 5 из 20
Для рекурсивного обхода дерева какой базовый случай естественнее всего?
F(None)=0
Вопрос 6 из 20
В каком порядке будут напечатаны числа?
Python
def show(n):
    if n == 0:
        return
    print(n, end=' ')
    show(n - 1)
    print(n, end=' ')

show(3)
Вопрос 7 из 20
Что вернёт outer(4)?
Python
def outer(n):
    local = n * 2
    if n == 1:
        return local
    result = outer(n - 1)
    return local + result

print(outer(4))
Вопрос 8 из 20
Почему глубина рекурсивного двоичного поиска равна O(log n)?
Вопрос 9 из 20
Какое значение x напечатает внешний вызов?
Python
def change(x):
    if x <= 1:
        return x
    y = change(x - 2)
    x = x + y
    return x

x = 5
result = change(x)
print(x, result)
Вопрос 10 из 20
Что обычно вызывает переполнение стека при корректной по смыслу рекурсии?
Вопрос 11 из 20
Какова асимптотика числа вызовов без мемоизации?
T(n)=T(n-1)+T(n-2)+O(1)
Python
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
Вопрос 12 из 20
Какая рекуррентность соответствует функции?
Python
def work(n):
    if n <= 1:
        return 1
    a = work(n // 2)
    b = work(n // 2)
    for _ in range(n):
        pass
    return a + b
Вопрос 13 из 20
Какова сложность T(n)=T(n−1)+O(1)?
Вопрос 14 из 20
Какова сложность функции при вычислении a**n?
Python
def power(a, n):
    if n == 0:
        return 1
    half = power(a, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * a
Вопрос 15 из 20
Что изменит мемоизация в наивном рекурсивном вычислении fib(n)?
Вопрос 16 из 20
Какой цикл эквивалентен хвостовой рекурсии?
Python
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
Вопрос 17 из 20
В каком порядке нужно положить детей в стек, чтобы нерекурсивный DFS посетил сначала левое поддерево, затем правое?
Python
# требуется тот же порядок: узел, левое поддерево, правое поддерево
Вопрос 18 из 20
Когда хвостовую рекурсию можно заменить циклом без явного стека?
Вопрос 19 из 20
Какой результат даст итеративная версия факториала?
5!=5\cdot4\cdot3\cdot2\cdot1
Python
n = 5
acc = 1
while n > 1:
    acc *= n
    n -= 1
print(acc)
Вопрос 20 из 20
Почему замена рекурсивного обхода произвольного дерева простым циклом с одной переменной current обычно недостаточна?

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу