Python 两次递归调用 - 参数的共享实例

Question

我正在尝试遍历二维矩阵的所有可能路径（条件是我只能向下或向右）。这是我正在尝试的：

rows = 3
columns = 3
# Class definition for node of the tree
class Node(object):
    def __init__(self):
        self.location = None
#  Starting the tree
tree = Node()
tree.location = [0,0]
def generateRestOfThePath(node):
    print 'Receiving node'
    print node.location
    if (node.location[0] >= rows) or (node.location[1] >= columns):
        print 'Out of playground', node.location
    elif node.location == [rows-1, columns -1]:
        print 'End of a path'
    elif  node.location[0] == rows-1:
        node.location[1] += 1
        print 'Reached bottom can only go right', node.location
        generateRestOfThePath(node)
    elif node.location[1] == columns -1:
        node.location[0] += 1
        print 'Reached right can only go down', node.location
        generateRestOfThePath(node)
    else:
        print 'Neither reached down nor right'  
        node.location[0] += 1
        print 'Going down', node.location
        generateRestOfThePath(node)
        print 'Finished with down', node.location
        node.location[1] +=1
        print 'Going Right', node.location  
        generateRestOfThePath(node)    
generateRestOfThePath(tree)

我得到的输出是这样的：

Receiving node
[0, 0]
Neither reached down nor right
Going down [1, 0]
Receiving node
[1, 0]
Neither reached down nor right
Going down [2, 0]
Receiving node
[2, 0]
Reached bottom can only go right [2, 1]
Receiving node
[2, 1]
Reached bottom can only go right [2, 2]
Receiving node
[2, 2]
End of a path
Finished with down [2, 2]
Going Right [2, 3]
Receiving node
[2, 3]
Out of playground [2, 3]
Finished with down [2, 3]
Going Right [2, 4]
Receiving node
[2, 4]
Out of playground [2, 4]

我遇到的问题是：

Finished with down [2, 2]

这不应该是[1, 0]吗？

我在想这个:

0,0
 | \ else case
 | 1,0 First recursion call
 | | \else case
 | | 2,0 First recursion call
 | | | only go right case
 | | 2,1 First and only recursive call
 | | | only go right case
 | | 2,2 First and only recursive call
 | | | End of path, No Recursion here
 | | / Since there is no recursion, the second recursion should be called (this is what I am thinking)
 | 1,0 Second recursion call
 | .........
 | .........
 |/

但这并没有发生。有人请给我指出正确的方向。

更新：

我认为与 C 或 C++ 不同的是 python 没有在内存中保留值 1,0 并且实际上只为节点的所有实例使用一个内存位置。我认为这是不同的实例，但根据 python 都是相同的实例。所以我认为这里真正的问题是。如何拥有不同的节点实例而不是共享一个？

Answer 1

我相信你的问题是，当你认为自己走对了，实际上你是在向右走，因为规则

node.location[0] += 1

也在这种情况下与

一起执行

node.location[1] += 1

编辑：抱歉，请快速阅读，误解了您的问题:)

print "finished with with down ..." 行仅在递归函数调用完成后执行。此函数调用仅在来自特定节点的 all 路径完成后才完成。因此，当您的脚本打印出行 finished with down [1,0] 时，它已经完成了所有可从 [1,0] 访问的节点。由于您不能从 [2,2] 向右或底部移动，因此该节点将始终先完成，因此首先打印出行 finished with [2,2]。

Answer 2

好的，因为问题只出在一个共享实例上，而且不超过一个实例，我已经拍了一张照片并用胶带记录了这种情况。我不认为这是一个理想的解决方案。我真的很想有人骂我，让我走上正确的道路。

这是我所做的：

"The key point here will be that we won't be storing any variables, we will only be passing values"

rows = 3
columns = 3

def generateRestOfThePath(node):
    rowNumber, columnNumber = node
    print 'Receiving node', rowNumber, columnNumber
    if (rowNumber >= rows) or (columnNumber >= columns):
        print 'Out of playground', rowNumber, columnNumber
    elif [rowNumber, columnNumber] == [rows-1, columns -1]:
        print 'End of a path'
    elif rowNumber == rows-1:
        columnNumber += 1
        print 'Reached bottom can only go right', rowNumber, columnNumber
        generateRestOfThePath([rowNumber, columnNumber])
    elif columnNumber == columns -1:
        rowNumber += 1
        print 'Reached right can only go down', rowNumber, columnNumber
        generateRestOfThePath([rowNumber, columnNumber])
    else:
        print 'Neither reached down nor right'  
        rowNumber += 1
        print 'Going down', rowNumber, columnNumber
        generateRestOfThePath([rowNumber, columnNumber])
        print 'Finished with down', rowNumber, columnNumber
        rowNumber -= 1
        columnNumber +=1
        print 'Going Right', rowNumber, columnNumber    
        generateRestOfThePath([rowNumber, columnNumber])
        print 'Finished with right'

generateRestOfThePath([0, 0])

Answer 3

正如我在评论中所说，此时，您只是在整个程序中创建了一个节点。如果你想为你通过的矩阵中的每个单元格创建一个新节点，你应该在对 generateRestOfThePath() 的调用中进行。对于下一个节点的每个可能值，生成该节点，然后使用该下一个节点调用 generateRestOfThePath。如果要在完整路径跟踪完成时打印起始值，则无法在递归函数中执行此操作。（这将在您每次完成从每个中间节点跟踪可能的延续时打印该语句。）

请允许我给你一点建议。您不需要 Node class。您可以只使用元组或列表。尽量使用python中的内置结构。它会让你的生活更轻松。

我不想给你写代码，因为那对你学习没有帮助。尝试一下，如果您运行遇到更多困难，请告诉我。祝你好运。

Python 两次递归调用 - 参数的共享实例

Python two recursion calls - shared instance of argument

python

recursion

tree-traversal