python - 在递归函数中返回或不返回

Question

在问之前，我搜索了一些旧问题，得到了一个更好的想法，将“return”放在前面，里面重新调用了函数，得到了预期的结果。其中一些喜欢: How to stop python recursion Python recursion and return statements .但是当我对我的问题做同样的事情时，情况会变得更糟。

我有一个二叉搜索树，想通过给定一个节点的键来获取 TreeNode 实例，所以它看起来更容易遍历需求，我已经很容易地实现了下面类似的功能，我没有在函数前面放 return :

#preorder_List=[]
def preorder(treeNode):
    if treeNode:
        preorder_List.append(treeNode.getKey())
        preorder(treeNode.has_left_child())
        preorder(treeNode.has_right_child())
    return preorder_List

所以对于我的新需求，我首先将其编写如下:

def getNode(treeNode,key):
    if(treeNode):
        if(treeNode.key==key):
            print("got it=",treeNode.key)
            return treeNode
        else:
            getNode(treeNode.left_child(),key)    
            getNode(treeNode.right_child(),key)

然后问题出现了，它找到了键/节点但一直运行并最终报告一个None错误然后我将return放在左右分支的前面，如下所示:

def getNode(treeNode,key):
    if(treeNode):
        if(treeNode.key==key):
            print("got it=",treeNode.key)
            return treeNode
        else:
            return getNode(treeNode.left_child(),key)    
            return getNode(treeNode.right_child(),key)   

但这让事情变得更糟，它确实到达了找到的键并更早地返回 None。

然后我尝试为分支删除一个“返回”，无论是右还是左。它有效(更新:当我的测试用例仅包含 3 个节点时，它有效，当我放置更多节点时，它不起作用，或者说预期的节点是否来自右侧，然后将 return 放在右侧分支调用之前，对于左边的，它没有)。什么是更好的解决方案？

Answer 1

您需要能够返回 递归调用的结果，但您并不总是需要无条件地这样做。有时您不会从第一个递归中获得所需的结果，因此您需要在返回任何内容之前对另一个递归进行递归。

处理此问题的最佳方法通常是将递归的结果分配给一个变量，然后您可以对其进行测试。因此，如果 getNode 要么返回一个节点(如果它找到了键)，要么返回一个节点 None(如果它没有找到)，你可以这样做:

result = getNode(treeNode.left_child(),key)    
if result is not None:
    return result
return getNode(treeNode.right_child(),key)

在这种特定情况下，由于 None 是错误的，您可以使用 或 运算符为您做“短路”:

return getNode(treeNode.left_child(),key) or getNode(treeNode.right_child(),key)

只有在第一个递归调用返回错误值(例如None)时才会进行第二次递归调用。

请注意，对于某些递归算法，您可能需要无条件递归多次，然后将结果组合在一起再返回。例如，将树中的(数字)键值相加的函数可能如下所示:

def sum_keys(node):
    if node is None:  # base case
        return 0
    left_sum = sumKeys(node.left_child())   # first recursion
    right_sum = sumKeys(node.right_child()) # second recursion
    return left_sum + right_sum + node.key  # add recursive results to our key and return