Как этот код доступен в этой функции рекурсии? - PullRequest
Новая
       15

Как этот код доступен в этой функции рекурсии?

0 голосов
/ 15 апреля 2020

Я делаю решатель судоку и нашел этот код в Интернете, который использовал метод, похожий на то, что я делал, но я не понимаю, как grid[y][x] = 0 может быть достигнуто в этом коде, так как он вызывает solve(grid) в строке ранее.

Я заметил, что получаю тот же вывод, если ставлю перед ним оператор else (а также, если он имеет меньший отступ) 

def solve(grid):
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y, x, n, grid):
                        grid[y][x] = n
                        solve(grid)
                        grid[y][x] = 0  # How is the program able to reach this code if it calls solve(grid) before it's able to be reached? 

                return

    print(np.matrix(grid))

Ответы [ 2 ]

2 голосов
/ 15 апреля 2020

Это рекурсивное решение. Рекурсивный означает, что функция решения сама вызывает. Он продолжает свой код, когда программа возвращается из вызова. 

grid[y][x] = n     # current solve changes grid
solve(grid)        # call recursively solve
                   # the function solve has now returned
                   # and can have changed grid 
grid[y][x] = 0     # now the current solve continues

Это работает, потому что список, такой как grid, является изменяемым объектом, что означает, что вызываемая функция может изменить сетку, и вызывающая сторона продолжает с измененной сеткой.

Существует одно условие: внутри решения должно быть какое-то условие, чтобы после многократного вызова самого себя возвращалось последнее вызванное решение.

Сравните это с хорошо известной функцией Фибоначчи: 

def F(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return F(n - 1) + F(n - 2)

print(F(6))

Он перестает называть себя, когда n == 0 или n == 1. До этого он продолжает называть себя n-1 и n-2.

0 голосов
/ 15 апреля 2020

Я не понимаю, что вас беспокоит - это просто обычный вызов функции. Очевидно, что функция может вызывать другую функцию, иначе мы не могли бы многое сделать.

NB: то, на что указывает имя solve, разрешается во время выполнения - единственное, что здесь происходит во время компиляции, это то, что сгенерированный байт-код знает, что он должен разрешить имя solve и применить вызов Операция, к которой относится это имя.

...