Бэктрекин без рекурсии на Python
В Python нет оптимизации хвостовой рекурсии и достаточно жёсткий лимит на рекурсивные вызовы. Это может вызвать затруднения при решении задач с помощью алгоритма бэктрекинга: лимита хватает на поиск решения судоку, но он может оказаться слишком низким, если количество решений для проверки в задаче довольно высоко. Тем не менее реализация бэктрекинга с рекурсией на Python элегантна, легко читаема и понятна. Отказываться от неё имеет смысл только для «тяжёлых» задач. def backtrack(self, solution): if solution in self.seen_solutions: return if self.reject(solution): return if self.accept(solution): self.output(solution) for child_solution in self.child_solutions(solution): self.backtrack(child_solution) Когда сложность задачи достигнет лимита рекурсивных вызовов, можно переключиться на шаблон без рекурсии. Он уже не так элегантен, как рекурсивное решение, но не так страшен, как мог бы быть. К тому же он использует те же вспомогательные функции, что и его собрат с рекурсией. ...