Рекурсия и динамическое программирование

Какую проблему решает алгоритм динамического программирования?

• Проблему, когда одно решение задачи зависит от решения других подзадач

• Проблему, когда задачи решаются без учета предыдущих решений

• Проблему поиска всех возможных решений задачи

• Проблему нахождения максимального пути в графе

s[0] = 2

s[1] = 3

s[n] = s[n-1]+s[n-2]

s[4] = ?

• 8
• 10
• 15
• 13

При исходном числе 3 результатом является 18 и при этом траектория вычислений содержит число 12.
Какое выражение следует использовать для вывода результата в задании 23?

• f(3,18)+f(12)

• f(3,12)*f(12,18)

• f(3,18)

• f(3,12)+f(12,18)

Рекурсия — это..

• функция, не возвращающая результат

• функция, не имеющая аргументов

• функция, которая вызывает саму себя

• функция, результат которой - рациональное число

Максимальная глубина рекурсии в Python по умолчанию

• 1000

• 500

• 1500

• 2000

Условие рекурсивного алгоритма

• Базовый случай

• Рекурсивный алгоритм всегда завершает работу без условий

• Базовый случай и рекурсивный вызов

• Базовый случай, специальный случай и рекурсивный вызов

Что такое базовый случай в рекурсивном алгоритме?

• Условие, при котором рекурсия прекращается

• Состояние, при котором функция вызывает себя

• Сложный случай, требующий дополнительных вычислений

• Случай, когда алгоритм работает бесконечно

Петя решил автоматизировать создание мемов. Он использует программу, которая каждую секунду удваивает количество мемов, но если число мемов делится на 8, программа зависает и не создаёт новые мемы.

Если Петя начал с 1 мемом, сколько мемов у него будет через 5 секунд?

• 4

• 16
• 32

• 8

Что произойдет, если в рекурсивной функции не будет базового случая?

• Функция завершится успешно

• Функция вызовет ошибку переполнения стека

• Функция будет работать быстрее

• Функция вернет ноль

Какой из следующих примеров является рекурсивной функцией?

• function f(x) { return x / 2; }

• function f(x) { return x + 1; }

• function f(x) { return f(x - 1) + 1; }

• function f(x) { return x * 2; }