Python遞歸和返回語句

我對Python和整個遞歸函數相當陌生，所以請原諒我的無知。Python遞歸和返回語句

我想在Python中實現二叉搜索樹，並有下列插入方法（取出一類）：

def insert(self, key, root=None): 
    '''Inserts a node in the tree''' 
    if root == None: 
     root = self.root 
    if root.key == None: 
     self._update(root, key) 
     return 0 
    else: 
     tmp = root 
     if key > tmp.key: # we work with the right subtree 
      self.insert(key, root=tmp.right) 
     elif key < tmp.key: # we work with the left subtree 
      self.insert(key, root=tmp.left) 
     else: # key already exists 
      return 0

我不知道這是否是清晰的，但它遍歷直到它變爲None值並使用要插入的鍵更新節點。

現在，該方法很好地工作，並從頭開始正確創建BST。但是，返回語句存在問題，因爲如果沒有執行遞歸，它只返回0。

>>> bst.insert(10) 
0 
>>> bst.insert(15) 
>>> bst.root.right.key 
15 
>>>

「插入」根密鑰再次返回0（從第15行）它應該的方式。

>>> bst.insert(10) 
0

我不明白爲什麼會發生這種情況。如果我在第6行中放置打印語句，它會正確執行，但它不會返回任何超過第一次插入的任何內容。爲什麼是這樣？（我敢肯定我沒有關於Python和遞歸的一些基本信息）

感謝您的幫助，

伊萬

PS：我讀過，遞歸是不是最好的辦法實施BST，所以我會研究其他解決方案，但在繼續之前，我想知道這個答案。

來源

2009-06-01 imiric

我不確定你認爲它應該返回，而不是0.你可以顯示你的期望？ – 2009-06-01 21:58:10

@imiric：我認爲你已經從其他人那裏得到了一些有用的指示，但是我還想指出，你的本能可以避開return語句，這可能表明你用表達式而不是語句來思考。如果是這樣，也許像Scheme這樣的語言會適合你。你當然不需要放棄Python，但是要保持對函數式編程語言的開放。 – 2009-06-02 02:29:54

在你的遞歸線上，你不會返回任何東西。如果你希望它返回0，你應該像行替換它們：

return self.insert(key, root=tmp.left)

，而不是僅僅

self.insert(key, root=tmp.left)

來源

2009-06-01 21:58:31

你是一個函數內，要返回一個值，你會怎麼做？你寫

def function(): 
    return value

在你的情況下，你想返回函數調用返回的值，所以你必須這樣做。

def function(): 
    return another_function()

然而，你

def function(): 
    another_function()

爲什麼你認爲應該工作？當然，你使用遞歸，但在這種情況下，你應該記住Python的禪，它只是說：

特殊情況是不夠特殊，以打破規則。

來源

2009-06-01 22:09:20 DasIch

Python遞歸和返回語句

回答

相關問題