Python recursion - как выйти с раннего

Question

Я играл с BST (двоичное дерево поиска), и мне интересно, как сделать ранний выход. Ниже приведен код, который я написал, чтобы найти kth самый маленький. Он рекурсивно вызывает дочерний узел find_smallest_at_k, а стек - это список, который передается в функцию, чтобы добавить все элементы inorder. В настоящее время это решение обрабатывает все узлы inorder, а затем я должен выбрать 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

Передача списка в качестве аргументов: Передача списка в качестве аргумента может быть хорошей практикой, , если вы сделаете вашу функцию хвостовой рекурсией. В противном случае это бессмысленно. С BST, где есть два возможных рекурсивных вызова функций, это немного высокий вопрос.

Иначе вы можете просто вернуть список. Я не вижу необходимости переменной i. В любом случае, если вам абсолютно необходимо возвращать значения кратных значений, вы всегда можете использовать кортежи, такие как return i, stack и это i, stack = root.find_smallest_at_k(k).

Fast-forwarding: Для быстрой пересылки обратите внимание, что правильные узлы родительского узла BST всегда больше родительского. Таким образом, если вы спускаете дерево всегда на правильных детей, вы получите растущую последовательность значений. Таким образом, первые k значения этой последовательности обязательно являются наименьшими, поэтому бессмысленно идти правильно k раз или более в последовательности.

Даже в середине вы спускаетесь, вы идете влево порой, бессмысленно идти больше, чем k раз справа. Свойства BST гарантируют, что, если вы поступите правильно, ВСЕ последующие номера ниже в иерархии будут больше, чем родительские. Таким образом, право направить k раз или больше бесполезно.

Код: Вот код псевдо-питона, быстро сделанный. Это не проверено.

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] 

EDIT Другая версия, следующая за моим комментарием.

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, это действительно поиск наименьшего элемента. Любое перемещение вправо немедленно вернет [], что ни к чему не способствует.

Answer 2

Как сказал Lærne, вам нужно заботиться о том, чтобы превратить вашу функцию в хвостовую рекурсивную; то вам может быть интересно, используя стиль продолжения прохождения. Таким образом, ваша функция может вызывать либо себя, либо функцию «escape». Я написал модуль под названием tco для оптимизации хвостовых вызовов; см. https://github.com/baruchel/tco Надеюсь, это поможет.