Что происходит со списком, когда он изменяется в аргументах рекурсивной функции - PullRequest
Новая
       85

Что происходит со списком, когда он изменяется в аргументах рекурсивной функции

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

Это решение вопроса n-queen. В рекурсивных вызовах он передает измененные списки. Мой вопрос для каждого рекурсивного вызова: создает ли он три новых списка: queens, xy_dif, xy_sum и сохраняет их в стеке вызовов? Или есть только эти три списка, каждый рекурсивный вызов только что изменил их? Если это так, я не понимаю, как это решает проблему, как показано ниже:

DFS ([], [], []) вызывает DFS ([0], [0], [0] ), то DFS ([0], [0], [0]) вызывает DFS ([0,2], [0, -1], [0,3]), так что условие if не прошло, поэтому возвращает.

Затем для l oop продолжить, q = 3, мой вопрос, почему DFS ([0,3], [0, -2], [0,4]) следующий вызов вместо DFS ([0,2,3], [0, -1, -2], [0,3,4])?

Как эти три списка вернулись к состоянию исходных состояний после вызова DFS ([0], [0], [0])? 

def solveNQueens(self, n):
    def DFS(queens, xy_dif, xy_sum):
        print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
        p = len(queens)
        print('updated row p is ', p)
        if p==n:
            result.append(queens)
            print('p==n, result is ', result)
            return None
        for q in range(n):
            print('loop starts, q is ', q)
            if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
    result = []
    DFS([],[],[])
    return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

1 Ответ

1 голос
/ 06 апреля 2020

Добавьте некоторое «стандартное» отслеживание рекурсии, и вы сможете легко увидеть результаты. В этом случае функция id является вашим другом и показывает, относится ли конкретный параметр к одной и той же сущности.

Как видно из приведенного ниже вывода, каждый параметр имеет уникальный идентификатор: это независимый объект. Это потому, что вы не передали параметры одного вызова другому. Скорее вы создали временную переменную в стеке. Если вы, например, просто наберете queens, то ссылка на список будет использоваться всеми вызовами.

С другой стороны, queens+[q] - это , а не queens; скорее, это новое выражение списка: временная переменная в стеке с отдельным значением.

Если вы хотите поделиться структурами, вы сначала измените queens, а затем передадите эту измененную версию в следующий уровень: 

queens.append(q)
DFS(queens, xy_dif+[p-q], xy_sum+[p+q])

В этом случае xy_diff и xy_sum по-прежнему являются независимыми переменными при каждом вызове, b ut queens совместно используется.

Ваш код с рекурсией контрольно-измерительные приборы: 

indent = ""

def DFS(queens, xy_dif, xy_sum):
    global indent
    print(indent, "ENTER DFS", queens, xy_dif, xy_sum)
    print(indent, "parameter IDs:", id(queens), id(xy_dif), id(xy_sum))
    indent += "  "

    print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
    p = len(queens)
    print('updated row p is ', p)

    if p==n:
        result.append(queens)
        print('p==n, result is ', result)
        indent = indent[2:]
        return None

    for q in range(n):
        print('loop starts, q is ', q)
        if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
            DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  

    result = []
    DFS([],[],[])
    send_back = [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

    print(indent, "LEAVE DFS", queens, xy_dif, xy_sum)
    indent = indent[2:]
    return send_back

начало вывода: 

 ENTER DFS [] [] []
 parameter IDs: 1813255818376 1813255818888 1813255819016
call function DFS([],[],[])
updated row p is  0
loop starts, q is  0
   ENTER DFS [0] [0] [0]
   parameter IDs: 1813255827784 1813258276680 1813255818760
call function DFS([0],[0],[0])
updated row p is  1
loop starts, q is  0
loop starts, q is  1
loop starts, q is  2
     ENTER DFS [0, 2] [0, -1] [0, 3]
     parameter IDs: 1813255817480 1813255817352 1813255817928
call function DFS([0, 2],[0, -1],[0, 3])
updated row p is  2
loop starts, q is  0
loop starts, q is  1
loop starts, q is  2
loop starts, q is  3
       ENTER DFS [] [] []
       parameter IDs: 1813255817864 1813255817736 1813255816712
call function DFS([],[],[])
updated row p is  0
loop starts, q is  0
         ENTER DFS [0] [0] [0]
         parameter IDs: 1813255816392 1813255816264 1813255816136
call function DFS([0],[0],[0])
...
...