- Установите соответствие между понятием рекурсии и его определением.
Левая колонка (А–Г): А) Базовый случай Б) Рекурсивный шаг В) Глубина рекурсии Г) Переполнение стека
Правая колонка (1–4):
- Обращение функции к самой себе с изменённым аргументом
- Ошибка, возникающая, когда число незавершённых вызовов превышает размер стека
- Условие, при котором функция возвращает результат, не вызывая себя
- Количество одновременно активных вызовов функции
- Установите соответствие между рекурсивной функцией и значением, которое она возвращает.
Левая колонка (А–Г): А) F(n) = F(n − 1) + 1, F(0) = 0; найти F(5) Б) F(n) = 2 · F(n − 1), F(0) = 1; найти F(4) В) F(n) = F(n − 1) + n, F(1) = 1; найти F(4) Г) F(n) = F(n − 1) + F(n − 2), F(1) = 1, F(2) = 1; найти F(6)
Правая колонка (1–4):
- 10
- 8
- 16
- 5
- Установите соответствие между рекурсивной процедурой и последовательностью, которую она выведет на экран (write выводит число).
Левая колонка (А–Г): А) procedure Print(n): if n > 0 then begin write(n); Print(n − 1) end; вызов Print(4) Б) procedure Print(n): if n > 0 then begin Print(n − 1); write(n) end; вызов Print(3) В) procedure Print(n): if n > 0 then begin write(n mod 2); Print(n div 2) end; вызов Print(6) Г) procedure Print(n): if n > 0 then begin Print(n div 2); write(n mod 2) end; вызов Print(6)
Правая колонка (1–4):
- 1 2 3
- 110
- 4 3 2 1
- 011
- Установите соответствие между задачей и её рекурсивной формулировкой.
Левая колонка (А–Г): А) Факториал числа n Б) Сумма цифр натурального числа n В) Наибольший общий делитель чисел a и b Г) Быстрое возведение в степень aⁿ
Правая колонка (1–4):
- НОД(a, b) = НОД(b, a mod b), НОД(a, 0) = a
- aⁿ = (a^(n/2))² при чётном n; aⁿ = a · a^(n−1) при нечётном n
- n! = n · (n − 1)!, 0! = 1
- S(n) = (n mod 10) + S(n div 10), S(0) = 0
- Установите соответствие между понятием и его описанием.
Левая колонка (А–Г): А) Мемоизация Б) Хвостовая рекурсия В) Дерево рекурсии Г) Бесконечная рекурсия
Правая колонка (1–4):
- Схема всех вызовов функции, показывающая её ветвления
- Сохранение ранее вычисленных значений, чтобы не вычислять их повторно
- Отсутствие или недостижимость условия остановки
- Рекурсивный вызов является последней операцией, и результат возвращается сразу
Ответы
- А–3, Б–1, В–4, Г–2
- А–4, Б–3, В–1, Г–2
- А–3, Б–1, В–4, Г–2
- А–3, Б–4, В–1, Г–2
- А–2, Б–4, В–1, Г–3