Анализировать рекурсивные функции и решать простые задачи динамического программирования (счёт вариантов, числа Фибоначчи-типа).
Рекурсия и динамическое программирование
Как работает рекурсия и зачем нужно ДП
Рекурсивная функция вызывает сама себя с изменёнными аргументами. Любая рекурсия должна иметь базовый случай — условие, при котором функция возвращает результат напрямую, без нового вызова. Без базового случая рекурсия была бы бесконечной. Дерево вызовов помогает отследить, сколько раз вызывается функция и в каком порядке. Например, f(4) вызывает f(3) и f(2); f(3) вызывает f(2) и f(1) — итого f(2) вызывается дважды.
Пример на Python (язык выбора на экзамене — на усмотрение, здесь для наглядности Python):
def f(n):
if n <= 1: return 1
return f(n-1) + f(n-2)
Это функция Фибоначчи-типа: f(0)=1, f(1)=1, f(2)=2, f(3)=3, f(4)=5. Заметим, что f(2) вычисляется повторно — это лишняя работа.
Динамическое программирование (ДП) устраняет повторные вычисления: мы один раз считаем каждое значение и сохраняем в таблицу. Для задачи «сколькими способами добраться до шага N, если можно делать шаг +1 или +2»: dp[0]=1, dp[1]=1, dp[2]=dp[1]+dp[0]=2, dp[3]=dp[2]+dp[1]=3 и т.д. Ключевой принцип: значение ячейки таблицы ДП зависит только от предыдущих уже заполненных ячеек.
Lesson notes
Как работает рекурсия и зачем нужно ДП
Рекурсивная функция вызывает сама себя с изменёнными аргументами. Любая рекурсия должна иметь базовый случай — условие, при котором функция возвращает результат напрямую, без нового вызова. Без базового случая рекурсия была бы бесконечной. Дерево вызовов помогает отследить, сколько раз вызывается функция и в каком порядке. Например, f(4) вызывает f(3) и f(2); f(3) вызывает f(2) и f(1) — итого f(2) вызывается дважды.
Пример на Python (язык выбора на экзамене — на усмотрение, здесь для наглядности Python):
def f(n):
if n <= 1: return 1
return f(n-1) + f(n-2)
Это функция Фибоначчи-типа: f(0)=1, f(1)=1, f(2)=2, f(3)=3, f(4)=5. Заметим, что f(2) вычисляется повторно — это лишняя работа.
Динамическое программирование (ДП) устраняет повторные вычисления: мы один раз считаем каждое значение и сохраняем в таблицу. Для задачи «сколькими способами добраться до шага N, если можно делать шаг +1 или +2»: dp[0]=1, dp[1]=1, dp[2]=dp[1]+dp[0]=2, dp[3]=dp[2]+dp[1]=3 и т.д. Ключевой принцип: значение ячейки таблицы ДП зависит только от предыдущих уже заполненных ячеек.