Python - рекурсия против Итерация в реализации связанного списка

#python #recursion #iteration

#python #рекурсия #итерация

Вопрос:

В чем разница в следующем коде? Ссылки относятся к объектам связанного списка. Атрибуты .first() и .rest() возвращают первое и остальные значения соответственно. В соответствии с политиками StackOverflow и политиками моего класса я хочу упомянуть, что это не задание — это было необязательное задание, которое было давно выполнено, и я возвращаюсь к нему, пробуя итерацию против рекурсии, чтобы подготовиться к предстоящему экзамену.

Вот несколько док-тестов.

 >>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False

Вот мое рекурсивное решение для функции def has_cycle(ссылка):

 existing = []
def cycle(link):
    nonlocal existing
    if link is not Link.empty:
        if link in existing:
            return True
        existing.append(link)
        cycle(link.rest)
cycle(link)
return False

Альтернативно

 existing = []
while link is not Link.empty:
    if link in existing:
        return True
    existing.append(link)
    link = link.rest
return False

Спасибо. Я должен упомянуть, что итеративная версия работает, рекурсивная версия — нет.

Класс списка ссылок:

 class Link:
    """A linked list.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.first
    1
    >>> s.rest
    Link(2, Link(3))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is Link.empty:
            return 'Link({})'.format(self.first)
        else:
            return 'Link({}, {})'.format(self.first, repr(self.rest))

1. Правильный ли отступ в вашем реальном коде?

2. Неверен ли размещенный мной отступ? Простите меня, я не совсем понимаю, на что вы ссылаетесь.

3. Я предполагаю, что Link.empty дает True или False ; если это так, ваше условие if link is not Link.empty никогда не будет выполняться, потому что link это не boolean . Просто измените это условие на if not Link.empty , и все готово.

4. В этом случае итеративное решение никогда не должно работать? Но это так. Я не думаю, что это все.

5. Ну, тогда покажите нам свой Link класс 🙂 Э-э-э … и вы должны return cycle(link.rest) (вернуть его результат, а не просто вызвать его).

Ответ №1:

 existing = []
def cycle(link):
    nonlocal existing
    if link is not Link.empty:
        if link in existing:
            return True
        existing.append(link)
        cycle(link.rest)
    else:
         return False

res = cycle(link)
#print res

Попробуйте это как свою рекурсивную версию….

1. Это сработало. Тьфу, это было просто. Спасибо за вашу помощь. Мне нужно было добавить еще один возврат к циклу (ссылка). Я пропустил, как работают возвраты в функциях более высокого порядка. Спасибо за ваше время.

Ответ №2:

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

 existing = []
def cycle(link):
    nonlocal existing
    if link is not Link.empty:
        if link in existing:
            return True
        existing.append(link)
        return cycle(link.rest) # Return result of recursive call
    else:
        return False # Return false if link is empty
print(cycle(link))