Урок 15: Рекурсия, backtracking и введение в DP
Вы добрались до итогового урока — отлично! Начнём с матрёшки: куклы, внутри которой кукла поменьше, и так до самой крошечной, которая уже не открывается. Это и есть «рекурсия»: функция, которая вызывает саму себя на меньшей версии той же задачи, а кукла, которая не открывается, — это «базовый случай
Рекурсия — как матрёшка: каждая кукла открывает меньшую, пока не дойдёшь до крошечной, которая не открывается (базовый случай). Backtracking — это попробовать путь, и если это тупик — закрыть его и попробовать другой. Memoization — это записать на бумажку уже вычисленные ответы, чтобы не вычислять их снова.
- рекурсия и backtracking
- Рекурсия: функция, которая вызывает саму себя на меньшей подзадаче до базового случая. Backtracking: сделать выбор, спуститься в рекурсию и отменить выбор, чтобы перебрать все возможности.
- базовый случай
- Условие, которое останавливает рекурсию и возвращает прямой ответ без нового вызова — без него рекурсия никогда не завершится.
- memoization
- Кэширование результатов подзадач (например, в dict), чтобы не вычислять их заново — это устраняет повторную работу и может значительно ускорить выполнение (например, наивный Fibonacci с O(2ⁿ) до O(n)).
