Рекурсия и backtracking

Recursion решает задачу через меньшие calls с base case. Backtracking исследует tree of choices, записывает candidate, делает recursion и затем отменяет choice. Он подходит для permutations, combinations, subsets, path search и constraint satisfaction.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Хорошие ответы определяют state, choices, stopping condition и pruning rule до кода. Также упоминают stack depth и когда iterative traversal безопаснее.

Типовые ошибки: Shared mutable arrays нужно копировать при сохранении results. Забытый undo state загрязняет следующие branches. Отсутствие base case дает infinite recursion.

Чеклист:

• Назовите state и choices.
• Запишите base case.
• Отменяйте mutations.
• Prune impossible branches.