Python - backtracking maze generation recursive function understanding

Question

I was looking for ways to create a maze in python.
I came across the code below at rosettacode.
I know the code use recursion to build the maze.
I understand the code lines and know what i'm reading and I want to use that code but i'm missing a key understanding of this code.

How exactly dose the recursive function in this code knows when to stop?

from random import shuffle, randrange

def make_maze(w = 16, h = 8):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

    def walk(x, y):
        vis[y][x] = 1

        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
        shuffle(d)
        for (xx, yy) in d:
            if vis[yy][xx]: continue
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "
            walk(xx, yy)

    walk(randrange(w), randrange(h))

    s = ""
    for (a, b) in zip(hor, ver):
        s += ''.join(a + ['\n'] + b + ['\n'])
    return s

if __name__ == '__main__':
    print(make_maze())

Answer 1

Applied debug printing to your code:

from random import shuffle, randrange

def make_maze(w = 3, h =3):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

    def debugPrint():
        print("-"*16)
        s = ""
        for (a, b) in zip(hor, ver):
            s += ''.join(a + ['\n'] + b + ['\n'])
        print(s )

        for r in vis:
            print(r) 


    def walk(x, y):
        debugPrint()

        vis[y][x] = 1

        d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
        shuffle(d)
        for (xx, yy) in d:
            if vis[yy][xx]: continue
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "

            walk(xx, yy)



    walk(randrange(w), randrange(h))

    s = ""
    for (a, b) in zip(hor, ver):
        s += ''.join(a + ['\n'] + b + ['\n'])
    return s

if __name__ == '__main__':
    print(make_maze())

to visualize whats happening:

----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+--+--+--+


[0, 0, 0, 1]
[0, 0, 0, 1]
[0, 0, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+--+
|  |  |  |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[0, 0, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+--+
|     |  |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+--+
|        |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 1, 0, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+--+
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |  |  |
+--+--+  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 0, 0, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|  |     |
+--+--+  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 0, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|        |
+--+--+  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[0, 1, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
----------------
+--+--+--+
|        |
+--+  +  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+


[1, 1, 1, 1]
[1, 0, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]

Final output:

+--+--+--+
|        |
+--+  +  +
|  |  |  |
+  +--+  +
|        |
+--+--+--+