BST查找递归函数对收益的困惑_python

我试图了解递归。 这是关于在Python中为BST实现查找功能的真正基本问题。 此代码直接从此。

在此示例中，查找函数返回两个值：（1）该值是否存在于树中；（2）如果在树中找到该值，则该父节点是什么。

为什么需要执行“返回self.left.lookup（data，self）”？ 您为什么不能只做“ self.left.lookup（data，self）”而没有返回值呢？

class Node:
    ...
    def lookup(self, data, parent=None):
        """
        Lookup node containing data

        @param data node data object to look up
        @param parent node's parent
        @returns node and node's parent if found or None, None
        """
        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
                return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

我实现了一个工作版本的查找，该版本不会在下面返回值的父节点。 下面的工作很好，而不必返回self.left.lookup（）：

def lookup(self, value):
    if(self.value == value):
        print("Found value!")
        return True
    elif self.value > value:
        if self.left == None:
            print("Value not found.")
            return False
        else:
            self.left.lookup(value)
    else:
        if self.right == None:
            print("Value not found.")
            return False
        else:
            self.right.lookup(value)

在下面的代码中，我尝试同时返回一个布尔值（无论该值是否在树中）以及父节点（就像原始帖子一样）：

def lookup(self, value, parent=None):
    if(self.value == value):
        print("Found value!")
        return True, parent
    elif self.value > value:
        if self.left == None:
            print("Value not found.")
            return False, None
        else:
            self.left.lookup(value, self)
    else:
        if self.right == None:
            print("Value not found.")
            return False, None
        else:
            self.right.lookup(value, self)

上面的代码不起作用，并且出现错误：“ TypeError：'NoneType'对象不可迭代”。 当我执行“ return self.right.lookup（value，self）”和“ return self.left.lookup（value，self）”时，TypeError消失了，但是我不明白为什么。 为什么添加“返回”可修复代码？

没有return语句，python自动返回None。 您可以在python shell中对此进行测试：

>>> def sum(a, b): a + b
>>> print sum(1, 2)
None

添加return语句告诉python将计算出的值返回给调用者：

>>> def sum(a, b): return a + b
>>> print sum(1, 2)
3

在您的情况下，正在发生的事情是要计算结果，但是一旦结束，它将被丢弃，因为对查询的中间调用未返回计算的结果。

为了说明玩具示例所发生的情况，请考虑一个简单的递归乘法函数：

>>> def mult(n, m, acc=0):                                                                                                                                                           
      if m == 0: return acc                                                                                                                                                        
      else:
        print("m %s: %s" % (m, acc))                                                                                                                                         
        mult(n, m-1, acc+n)

在这里，对mult的中间调用不会返回递归步骤所计算的结果。 调用该函数将产生以下输出：

>>> print mult(3, 3)
m 3: 0
m 2: 3
m 1: 6
None

如您所见，结果正在计算中，但是一旦最终结果准备好，一切都将被丢弃。

添加return语句：

>>> def mult(n, m, acc=0):                                                                                                                                                          
      if m == 0: return acc                                                                                                                                                        
      else:
        print("m %s: %s" % (m, acc))                                                                                                                                         
        return mult(n, m-1, acc+n)

产生预期的输出：

print mult(3, 3)
m 3: 0
m 2: 3
m 1: 6
9

通常，递归函数的每个步骤都必须按原样（尾递归）或以某种方式修改后返回后续步骤的结果。

BST查找递归函数对收益的困惑

问题描述

1楼