В 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)
Когда сложность задачи достигнет лимита рекурсивных вызовов, можно переключиться на шаблон без рекурсии. Он уже не так элегантен, как рекурсивное решение, но не так страшен, как мог бы быть. К тому же он использует те же вспомогательные функции, что и его собрат с рекурсией.
def backtrack(self, solution):
solution_stack = [self.child_solutions(solution)]
while True:
current_generator = solution_stack[-1]
solution = next(current_generator, None)
while solution:
if self.reject(solution):
solution = next(current_generator, None)
continue
if self.accept(solution):
self.output(solution)
if not self.solution_is_complete(solution):
solution_stack.append(self.child_solutions(solution))
current_generator = solution_stack[-1]
solution = next(current_generator, None)
solution_stack = solution_stack[:-1]
if not solution_stack:
return