Idiomatic backtracking in Python

[Chris Angelico]

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