Рекурсивная функция не работает, несмотря на пустой тест стека - PullRequest
Новая
       17

Рекурсивная функция не работает, несмотря на пустой тест стека

0 голосов
/ 05 октября 2019

Я не знаю, почему строка if len(stack)==0: return 0 не работает.

Элементы списка графиков представляют узлы, например: [2, 6] означает, что узел со значением 2 -> узел со значением6, аналогично узел со значением 4 связан с узлами со значением 7, 8, 9 (три узла-потомка).

Интересно, существует ли маршрут от goal[0] до goal[1] или нет.

В моем примере маршрут отсутствует. 

graph_list=[[2, 6], [4, 7], [5, 7], [1, 5], [2, 9], [4, 9], [4, 8], [5, 3], [7, 8]]
goal=[1, 9]

stack=[goal[0],]

def check_func(d_list, goal):

    if len(stack)==0:
        return 0

    for node in d_list:
        if node[0]==stack[-1]:
            stack.append(node[1])
            d_list.remove(node)
            check_func(d_list, goal)

    if stack[-1]==goal[1]:
        return 1

    else:
        stack.pop(-1)
        print(stack)
        check_func(d_list, goal)

После некоторых итераций в следующей строке возникает ошибка.

если стек [-1] == цель [1]:
IndexError: индекс списка вне диапазона

Я не понимаю, почему возникает эта ошибка,Я думаю, что первая строка кода функции предотвращает ошибку.

1 Ответ

1 голос
/ 06 октября 2019

Я вижу несколько проблем с вашим кодом:

  • Распространенная ошибка новичков в рекурсии: ваш check_func() возвращает значение, но когда вы вызываете его рекурсивно, вы игнорируете возвращенное значение!

  • Удаление элементов из d_list в цикле, по которому вы проходите d_list, обычно плохая идея. И, в этом случае, не нужно.

  • Пробное добавление к логике стека имеет недостатки, поскольку вы не удаляете добавленный элемент при рекурсивном сбое и продолжаете тестирование.

  • Ваш пример graph_list никогда не будет успешным с целью [1, 9] - полезный тестовый пример, но не очень хороший для разработки. Вместо этого попробуйте цель [1, 8].

Ниже приведена моя переделка вашего кода, посмотрите, будет ли он вести себя так, как вам хочется: 

def check_func(d_list, goal):

    if not stack:
        return False

    if goal[1] == stack[-1]:
        return True

    for node in d_list:
        if node[0] == stack[-1]:
            stack.append(node[1])
            if check_func(d_list, goal):
                return True
            stack.pop()

    return False

graph_list = [[2, 6], [4, 7], [5, 7], [1, 5], [2, 9], [4, 9], [4, 8], [5, 3], [7, 8]]

goal = [1, 8]

stack = [goal[0]]

if check_func(graph_list, goal):
    print(stack)

ВЫХОД 

> python3 test.py
[1, 5, 7, 8]
>
...