Возвращать или не возвращать в рекурсивной функции - PullRequest
Новая
       17

Возвращать или не возвращать в рекурсивной функции

0 голосов
/ 03 июня 2018

Прежде чем спрашивать, я искал несколько старых вопросов и получил лучшую идею поместить «return» перед внутренней частью, повторно вызвав функцию, чтобы получить ожидаемый результат.некоторые из них, например: Как остановить рекурсию Python Операции рекурсии Python и оператор возврата .Но когда я делаю то же самое с моей проблемой, она ухудшается.

У меня есть дерево бинарного поиска, и я хочу получить экземпляр 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 перед правым вызовом ветвления работает,для левого, это не так).Какое решение лучше?

Ответы [ 3 ]

0 голосов
/ 04 июня 2018

Не зная больше о ваших объектах:

Три базовых случая:

  • текущий узел равен None -> return None
  • текущий узел соответствуетключ -> вернуть его
  • текущий узел не совпадает, это конец ветви -> вернуть нет

Если не базовый случай, рекурсивный.Замкните накоротко рекурсию с помощью or: верните левую ветвь, если она совпадает, или верните результат правой ветки (который также может быть None) 

def getNode(treeNode,key):
    if treeNode == None:
        return None
    elif treeNode.key == key:
        print("got it=",treeNode.key)
        return treeNode
    elif not any(treeNode.has_left_child(), treeNode.has_right_child()):
        return None
    #left_branch = getNode(treeNode.left_child(),key)    
    #right_branch = getNode(treeNode.right_child(),key)
    #return left_branch or right_branch
    return getNode(treeNode.left_child(),key) or getNode(treeNode.right_child(),key)
0 голосов
/ 04 июня 2018

Вы должны иметь возможность return результатов ваших рекурсивных вызовов, но вам не всегда нужно делать это безоговорочно.Иногда вы не получите нужный вам результат из первой рекурсии, поэтому вам нужно выполнить рекурсию для другой, прежде чем что-либо возвращать.

Лучший способ справиться с этим, как правило, - присвоить результаты рекурсии.к переменной, которую вы можете затем проверить.Поэтому, если getNode либо возвращает узел (если он нашел ключ), либо None (если он этого не сделал), вы можете сделать что-то вроде этого: 

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

В этом конкретном случаепоскольку None означает «ложь», вы можете использовать оператор «1010 *» для выполнения «короткого замыкания» за вас: 

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
0 голосов
/ 04 июня 2018

Вместо return используйте yield: 

class Tree:
   def __init__(self, **kwargs):
      self.__dict__ = {i:kwargs.get(i) for i in ['left', 'key', 'right']}

t = Tree(key=10, right=Tree(key=20, left=Tree(key=18)), left=Tree(key=5))
def find_val(tree, target):
  if tree.key == target:
    yield target
    print('found')
  else:
    if getattr(tree, 'left', None) is not None:
      yield from find_val(tree.left, target)
    if getattr(tree, 'right', None) is not None:
      yield from find_val(tree.right, target)

print(list(find_val(t, 18)))

Вывод: 

found
[18]

Однако вы также можете реализовать функцию get_node в качестве метода в вашемКласс двоичного дерева путем реализации __contains__ методов: 

class Tree:
   def __init__(self, **kwargs):
     self.__dict__ = {i:kwargs.get(i) for i in ['left', 'key', 'right']} 
   def __contains__(self, _val):
     if self.key == _val:
        return True
     _l, _r = self.left, self.right
     return _val in [[], _l][bool(_l)] or _val in [[], _r][bool(_r)]

t = Tree(key=10, right=Tree(key=20, left=Tree(key=18)), left=Tree(key=5))
print({i:i in t for i in [10, 14, 18]})

Вывод: 

{10: True, 14: False, 18: True}
...