Python中的遞歸如何工作

我想解決一個面試問題：如何將BST轉換爲雙鏈表。以下是我的代碼。我非常困惑python遞歸如何工作。爲什麼在convert2DoubleLst_recursive之後，prev和head仍然是None，我爲這兩個變量分配了一個新值，爲什麼在這個方法調用之後，我無法保存這個變化。我記得python通過引用傳遞參數，但爲什麼在這裏我無法保存更改。提前謝謝了。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)

來源

2014-01-17 lexie

請修復您的縮進 - 此代碼不會編譯。 – BartoszKP

「我記得python通過引用傳遞參數」你錯誤地記住了。（我推薦閱讀http://stackoverflow.com/a/986145/110707） – geoffspear

我想你可以通過傳遞包含在列表或字典中的兩個參數來模擬傳遞引用類似的行爲。但你不應該。 –

天真地說，因爲在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。

來源

2014-01-17 15:38:37 hop

Python中的遞歸如何工作

回答

相關問題