Backtracing without Recusion in Python

Posted on Thu, 03 Nov 2016 in Python

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