python - Python 中的递归是如何工作的

Question

我正在尝试解决一个面试问题:如何将 BST 转换为双链表。下面是我的代码。我真的很困惑 python 递归是如何工作的。为什么在convert2DoubleLst_recursive之后，prev和head仍然是None，我已经为这两个变量分配了新值，为什么在这个方法调用之后，我无法保存更改。我记得 python 通过引用传递参数，但为什么在这里我无法保存更改。非常感谢。

def convert2_recursive(node):
    prev,head=None,None
    convert2DoubleLst_recursive(node,prev,head)
    end=head.lChild
    printList(head,end)

def convert2DoubleLst_recursive(node,prev,head):
    if node:
        convert2DoubleLst_recursive(node.lChild,prev,head)
        node.lChild=prev
        if prev:
           prev.rChild=node
        else:
           head=node
        nextNode=node.rChild
        head.lChild=node
        node.rChild=head
        prev=node
        convert2DoubleLst_recursive(nextNode,prev,head)

Answer 1

天真地说，因为Python中没有引用传递。递归不是你的问题。

当你想到“Python 中没有变量，只有名称和值”时，情况可能会变得更清晰一些。

当声明convert2DoubleLst_recursive(node.lChild, prev, head)时执行后，实际上是函数convert2DoubleLst_recursive被调用的值是 node.lChild , prev和head指向当时。

然后，在convert2DoubleLst_recursive内，这些值被赋予(本地)名称 node等等(与以前的名称不同!)。

稍后，您为这些名称分配新值，进行递归(这实际上与您的代码无关)，并且本质上 Python 在退出函数时会忘记这些名称及其值。

基本上，在第 8 行和第 10 行之间 prev不会改变它的值(正如您所经历的)，因为调用者中使用的名称在被调用者内部永远不会看到。分配给该名称的值在第 3 行中没有更改，并且与被调用者内部发生的情况无关。

如果您想将值传递回调用者，您必须 return他们。

或者您可以替换 None由一个监护对象，其行为类似于您的节点类并代表 None .

不过，通常情况下，在 Python 中可以使用比链表更好的数据结构。(例如，Python list 内部已经是链表，可以使用它来代替。)

更深入的分析可以在这里找到:https://stackoverflow.com/a/986145/110707 .