Recursion head scratcher

[Joel Madigan]

Hi everyone!
Sorry this isn't strictly a Python question but my algorithms professor
contends that given the standard recursive-backtracking maze solving
algorithm:

width=6
height=4
maze=[[1,0,1,1,0,1],
      [0,0,1,0,0,0],
      [1,0,1,0,1,0],
      [0,0,0,0,1,1]]
visited = [[False for x in range(width)] for y in range(height)]

sx=1
sy=2
ex=4
ey=0

def findPath(x,y):
    if (x < 0 or x >= width or y < 0 or y >= height):
        return False
    elif maze[y][x] == 1:
        return False
    elif visited[y][x]:
        return False
    elif (x == ex and y == ey):
        print "(%d,%d)"%(x,y),
        return True
    else:
        visited[y][x] = True

        if findPath(x-1,y) or \
           findPath(x+1,y) or \
           findPath(x,y-1) or \
           findPath(x,y+1):
            print "(%d,%d)"%(x,y),
            return True
        else:
            return False

print findPath(sx,sy)

that it is possible to make it print the path to the finish in the order the
steps were taken.  That is, the algorithm as written produces:
(4,0) (4,1) (3,1) (3,2) (3,3) (2,3) (1,3) (1,2) True

Rather than
(1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (4,1) (4,0) True

Furthermore, he claims it's a "one line change" without using a stack or any
other extra data structure.  But I can't figure it out to save my life.
 This isn't homework, there isn't credit on the line.  I think he said it
just to mess with us.  Can anyone point me in the right direction?  It's
driving me crazy.  The output it gives makes perfect sense, since it just
prints out each step as the stack unwinds.  Normally you would print the
output BEFORE recursing, but in this case you only want to print the step if
it is actually part of the path.  And you don't know that until after the
recursion.

Can anyone shed some light on this?

Thanks,
Joel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20091202/2e5d3a12/attachment.html>