Рекурсия и 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 — это один шаблон с разными правилами выбора.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.