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递归和返回语句

回答

相关问题