Возврат кортежа списка в функции рекурсии

Question

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

class LinkNode(object): 
"""A node in a linked list.""" 

def __init__(self, item, next=None): 
    """(LinkNode, object, LinkNode) -> NoneType 
    Initialize this node to store item and next. 
    """ 
    self.item = item 
    self.next = next 

def odd_or_even(self): 
    """(LinkNode) -> ([object], [object]) 
    Return a pair of lists: (odd number, even number. 
    """ 
    if self is None: 
     return ([], []) 
    else: 
     if (self.item % 2 == 1): 
      odd_num = odd_num.append(self.item) 
     else: 
      even_num = even_num.append(self.item) 
    if self.next is not None: 
     self.next.odd_or_even() 
    return (odd_num, even_num) 

Когда я запускаю его, я получил следующее сообщение об ошибке:

Файл "C: \ Program Files \ Wing IDE 101 4,1 \ SRC \ Debug \ tserver_sandbox.py", строка 19, в odd_or_even builtins.UnboundLocalError: локальная переменная 'odd_num', на которую ссылаются до назначения

Где я должен начинать odd_num, even_num, поэтому он не будет перезаписан?

Спасибо.

Answer 1

Я думаю, что есть несколько разных подходов, которые вы могли бы использовать.

Можно было бы использовать глобальные переменные. Я не рекомендую, но это легко понять, так что первый я представляю это:

even_num = [] # these should be at module level, but I'm not showing the class 
odd_num = [] # so you'll have to imagine the indentation being correct 

def odd_or_even(self): 
    """(LinkNode) -> ([object], [object]) 
    Return a pair of lists: (odd number, even number. 
    """ 
    if self.item % 2 == 1: 
     odd_num.append(self.item) 
    else: 
     even_num.append(self.item) 

    if self.next is not None: 
     self.next.odd_or_even() 

Изменения в коде незначительны, в основном только удаление return заявления. Я вынул первоначальную проверку для self, являющейся None, поскольку это невозможно в методе (если вызывающий не пытается сделать это очень сложно). Также стоит отметить, что мы не пытаемся напрямую назначить odd_num или even_num, так как это создало бы локальную переменную, а не доступ к уже существующим глобальным переменным. Недостатком этого решения является то, что вы можете позвонить только odd_or_even и заставить его работать правильно. Если вы хотите снова позвонить (возможно, в другом списке), вам необходимо повторно инициализировать глобальные переменные.

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

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

def odd_or_even(self, lists=None): 
    if lists is not None: 
     even_num, odd_num = lists 
    else: 
     even_num = [] 
     odd_num = [] 

    if self.item % 2 == 1: 
     odd_num.append(self.item) 
    else: 
     even_num.append(self.item) 

    if self.next is not None: 
     return self.next.odd_or_even((even_num, odd_num)) 
    else: 
     return even_num, odd_num 

Это более эффективно, чем в предыдущей версии, так как он использует тот же список на всех уровнях рекурсии. В некоторых других языках программирования этот стиль рекурсии, где все работы выполняются до запуска рекурсивного вызова, намного эффективнее других рекурсий.Это связано с тем, что компилятор может оптимизировать шаг return функции (и просто повторно использовать фрейм стека). Тем не менее, Python не выполняет такую ​​«оптимизацию хвостовых вызовов» (потому что это испортит трассировку стека), поэтому преимущества не такие большие, как они могут быть.

Другое дело: вы можете использовать свой собственный класс связанных списков, а не списки Python для хранения четных и нечетных значений. Как второе, так и третье решения, которые я показал выше, могут работать, хотя третий будет работать наиболее естественно, если вы захотите вернуть четные и нечетные значения в обратном порядке.

Answer 2

if (self.item % 2 == 1): 
     odd_num = odd_num.append(self.item) 
    else: 
     even_num = even_num.append(self.item) 
... 
return (odd_num, even_num) 

выше раздел кода устанавливает значение либо odd_num или even_num, но не оба. Затем он пытается вернуть оба значения odd_num и even_num, что приводит к ошибке для той или иной. Если вы инициализируете оба значения до None перед этим оператором if, вы избежите возникшей ошибки. Однако, чтобы заставить семантику работать, вам может потребоваться добавить еще один параметр в вашу функцию, а именно результат предыдущего уровня; в рекурсивном вызове передать только что вычисленный odd_num или even_num до следующего уровня; затем верните результат следующего уровня вниз. Однако лучше избегать рекурсии и вместо этого иметь цикл, который выполняется дважды.