Алгоритмы с нуля
Рекурсия и backtracking: тест на припоминание
Припоминание лучше перечитывания. На каждый промпт скажите или запишите полный ответ по памяти, прежде чем откроете модельный ответ. Именно усилие извлечения закрепляет материал.
Восстановите по памяти ключевые механизмы юнита: две обязательные части рекурсии, как call stack превращает глубину в память, как дерево рекурсии превращает ветвление во время, и шаблон backtracking с pruning.
- 01Каковы две обязательные части любой рекурсивной функции и что идёт не так, если одной из них нет?
- 02Объясните recursive leap of faith и почему он упрощает написание рекурсивного кода.
- 03Как call stack определяет пространственную сложность рекурсивной функции и что такое stack overflow?
- 04Как прочитать временную сложность рекурсивной функции по её дереву рекурсии?
- 05Сформулируйте шаблон backtracking и объясните, почему шаг undo обязателен.
- 06Что такое pruning в backtracking и чем различаются subsets, permutations и combinations в одном шаблоне?
Если вы восстановили каждый ответ по памяти, вы держите хребет юнита: base case плюс настоящий прогресс обеспечивают завершение рекурсии; call stack превращает максимальную глубину в O(глубина) памяти; дерево рекурсии превращает branching factor и глубину во время b^d; а backtracking — это тот же рекурсивный скелет, применённый как choose-explore-undo, с pruning для пропуска обречённых веток и копиями для безопасной записи результатов. Subsets, permutations и combinations — это один шаблон с разными правилами выбора.