Skip to main content
 首页 » 编程设计

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

2024年12月31日10落叶无声

在问之前,我搜索了一些旧问题,得到了一个更好的想法,将“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 放在右侧分支调用之前,对于左边的,它没有)。什么是更好的解决方案?

请您参考如下方法:

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

处理此问题的最佳方法通常是将递归的结果分配给一个变量,然后您可以对其进行测试。因此,如果 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