On 01/25/2015 08:45 PM, Chris Angelico wrote:
On Mon, Jan 26, 2015 at 12:31 PM, Marko Rauhamaa <ma...@pacujo.net> wrote:
Backtracking means the part of depth-first traversal where you retreat
to the parent node. If you implement your traversal with a recursive
function, backtracking means — more or less — a return from the
function.
But possibly you need to return from N levels, not just one. Imagine
you're traversing a directory tree using a simplistic recursive
algorithm:
def traverse(dir):
for d in subdirs(dir): traverse(d)
for f in files(dir):
if file_size(f) > 1024*1024*1024: skip this entire branch of the tree
Obviously you have to define the branch somehow, but there are plenty
of times when you might want to break out of "everything up to here".
How do you define that? How do you return lots of levels all at once?
I remember facing this exact problem in trying to solve a particular
piece-layout puzzle; if I discovered an impossible situation, I could
actually discard at least two or three levels of recursion all at
once, because there's no way that the situation could become
un-impossible within those levels. Can't remember how I ended up
dealing with that... I think I got naughty and used a global variable.
When I've done things like that, there was no need to do a "return
multiple". You just return, and your caller happens to be a the end of
his loop, so he returns also.
Classic example of this is the 8 queens puzzle. Each level is going to
examine one row, and once there are no places that aren't yet attacked,
it simply returns.
--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list
