Are backtracking algorithms always using recursion?

Question

All backtracking algorithms that I used so far were based on recursion. But I wasn't able to find any evidence that backtracking cannot be non-recursive. So the question is whether backtracking algorithms are always using recursion?

Answer 1

Nope, backtracking can be done without recursion. Here is an example: Non-recursive backtracking, using a stack:

boolean solve(Node n) {
    put node n on the stack;
    while the stack is not empty {
        if the node at the top of the stack is a leaf {
            if it is a goal node, return true
            else pop it off the stack
        }
        else {
            if the node at the top of the stack has untried children
                push the next untried child onto the stack
            else pop the node off the stack

    }
    return false
}

A real example

The N-Queens Problem

• recursive solution
• non-recursive solution

And as I tested, the non-recursive solution is significantly faster. I am not saying that non-recursive solution is always faster, but it does offer more flexibility for performance optimization(instead of saving the whole call stack, you decide what to put into the stack).