Idiomatic backtracking in Python

Chris Angelico rosuav at gmail.com
Mon Jan 26 02:45:03 CET 2015


On Mon, Jan 26, 2015 at 12:31 PM, Marko Rauhamaa <marko at 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.

ChrisA



More information about the Python-list mailing list