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?
Asked
Active
Viewed 1,448 times
2
-
14Every recursive algorithm can be automatically rewritten in a non-recursive one: simply push and pop data that you would have pushed/popped on the call stack on a regular stack. – Willem Van Onsem Sep 07 '17 at 10:30
-
2Recursion is just a matter of implementation. It lends itself well for backtracking, and that's why you will generally see recursion in those algorithms. However, like @WillemVanOnsem says, there's noone forcing you to implement it using recursion. – Glubus Sep 07 '17 at 10:37
-
1https://en.wikipedia.org/wiki/Backtracking#Description_of_the_method – DAle Sep 07 '17 at 11:00
-
iterative version of [grid A* is backtracking](https://stackoverflow.com/a/28317199/2521214) without any recursion ... it is simple `O(n)` loop without any stack ... – Spektre Sep 08 '17 at 06:25
1 Answers
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
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).
Tyler Liu
- 19,552
- 11
- 100
- 84