时间戳

首页 > 解决方案 > 尽管空堆栈测试，递归函数不起作用

python - 尽管空堆栈测试，递归函数不起作用

问题描述

我不知道为什么这条线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)

经过一些迭代后，在以下行，出现错误。

if stack[-1]==goal[1]:
IndexError: list index out of range

我不明白为什么会发生此错误。我认为功能代码的第一行可以防止错误。

标签： pythonrecursionindexingrange

解决方案

我发现您的代码存在几个问题：

  • 递归初学者的一个常见错误：你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]
>

推荐阅读