Python 递归 - 如何提前退出

Question

我一直在玩 BST（二叉搜索树），我想知道如何提前退出。以下是我为找到第 k 个最小值而编写的代码。它递归调用子节点的find_smallest_at_k，stack只是一个传入函数的列表，将所有元素按顺序相加。目前这个解决方案按顺序遍历所有节点，然后我必须 select 来自 "stack" 的第 k 个项目在此函数之外。

def find_smallest_at_k(self, k, stack, i):
    if self is None:
        return i

    if (self.left is not None): 
        i = self.left.find_smallest_at_k(k, stack, i) 

    print(stack, i)
    stack.insert(i, self.data)
    i += 1
    if i == k: 
        print(stack[k - 1]) 
        print "Returning" 

    if (self.right is not None): 
        i = self.right.find_smallest_at_k(k, stack, i) 

    return i

是这样叫的，

our_stack = []
self.root.find_smallest_at_k(k, our_stack, 0) 
return our_stack[k-1]

我不确定是否可以提前退出该功能。如果我的 k 是 1，我真的不必遍历所有节点然后找到第一个元素。从外部函数传递列表也感觉不对 - 感觉就像将指针传递给 C 中的函数。有人能提出比我目前所做的更好的替代方案吗？

Answer 1

将列表作为参数传递：将列表作为参数传递是一种很好的做法，如果您使函数 tail-recursive .否则没有意义。对于 BST，其中有两个潜在的递归函数调用要完成，这是一个有点高的要求。

否则你可以 return 列表。我没有看到变量 i 的必要性。无论如何，如果你绝对需要 return 多个值，你总是可以使用这样的元组 return i, stack 和这个 i, stack = root.find_smallest_at_k(k).

Fast-forwarding: 对于 fast-forwarding，请注意 BST parent 节点的右节点总是大于 parent.因此，如果你总是在右边 children 下树，你最终会得到一个不断增长的值序列。因此，该序列的第一个 k 值必然是最小的，因此在一个序列中向右 k 次或更多次是没有意义的。

即使在下降的中间，您有时也会向左走，向右走超过 k 次是没有意义的。 BST 属性确保如果您向右走，层次结构中下方的所有后续数字都将大于 parent。所以右转k次以上是没用的

代码： 这是一个快速制作的 pseudo-python 代码。未测试。

def findKSmallest( self, k, rightSteps=0 ):
    if rightSteps >= k: #We went right more than k times
        return []
    leftSmallest = self.left.findKSmallest( k, rightSteps ) if self.left != None else []
    rightSmallest = self.right.findKSmallest( k, rightSteps + 1 ) if self.right != None else []
    mySmallest = sorted( leftSmallest + [self.data] + rightSmallest )
    return mySmallest[:k]

根据我的评论编辑另一个版本。

def findKSmallest( self, k ):
    if k == 0:
        return []
    leftSmallest = self.left.findKSmallest( k ) if self.left != None else []
    rightSmallest = self.right.findKSmallest( k - 1 ) if self.right != None else []
    mySmallest = sorted( leftSmallest + [self.data] + rightSmallest )
    return mySmallest[:k]

注意如果k==1，这确实是最小元素的查找。任何向右移动，将立即 returns []，这没有任何贡献。

Answer 2

正如 Lærne 所说，您必须注意将函数转换为尾递归函数；那么您可能会对使用连续传递样式感兴趣。因此，您的函数可以调用自身或 "escape" 函数。我编写了一个名为 tco 的模块来优化尾调用；见 https://github.com/baruchel/tco 希望对你有帮助。

Answer 3

这是另一种方法：它不会提前退出递归，而是在不需要时阻止额外的函数调用，这实际上就是您要实现的目标。

class Node:
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None

def find_smallest_at_k(root, k):
    res = [None]
    count = [k]

    def helper(root):
        if root is None:
            return

        helper(root.left)
        count[0] -= 1
        if count[0] == 0:
            print("found it!")
            res[0] = root
            return

        if count[0] > 0:
            print("visiting right")
            find(root.right)

    helper(root)
    return res[0].v

Answer 4

如果您想尽快退出，请使用exit(0)。这将使您的任务变得简单！

Python 递归 - 如何提前退出

Python recursion - how to exit early

python

recursion

exit

binary-search-tree