As you know there is no tail recursion optimization in Python. Moreover it has a very low recursion limit. It can be a problem if you are trying to solve the problem using the backtracking algorithm. Recursion limit is big enough to solve sudoku, but an exception will raise if the problem has more possible solutions.
However implementation of backtracking in Python with recursion is elegant. It's easy to read and understand.
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)
When you rich recursion limit, you can switch to this template without recursion. It doesn't look so clean as one with recursion, but it's not so ugly than it could be, and it uses the same auxiliary functions.
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
Got a question? Hit me on Twitter: avkorablev