时间戳

首页 > 解决方案 > 递归函数中的返回冲突

python - 递归函数中的返回冲突

问题描述

我正在编写一个函数来解决单词搜索问题。但是，我遇到了如何从我的 dfs 递归函数中正确获取返回值的困境。这是问题所在：如果我return在代码的最后一行使用关键字，for direction in [[0,1],[0,-1],[1,0],[-1,0]]一旦返回被击中，它就会过早结束循环。但是，如果我删除return最后一行中的，递归函数将正常工作，但即使满足语句，它也永远不会True从 语句返回。if len(word)==0:print("TRUE") return True我基本上明白，一旦程序return运行，它将忽略它之后的所有代码。你能解释一下如何摆脱这个陷阱吗？

def dfs(cur, board, word):
    board[cur[0]][cur[1]] = None
    print(cur, board, word)
    if len(word)==0:
        print("TRUE")
        return True   

    for direction in [[0,1],[0,-1],[1,0],[-1,0]]:
        Doard = copy.deepcopy(board)
        x = cur[0]+ direction[0]
        y = cur[1]+ direction[1]
        if x>len(board)-1 or x<0 or y>len(board[0])-1 or y<0:
            continue
        if Doard[x][y] == word[0]:
            Doard[x][y] = None
            return dfs([x,y], Doard, word[1:])  # Problematic RETURN keyword here

标签： pythonrecursionreturn

解决方案

@kszl 给你的建议很好，检查递归调用的结果，如果是，则只返回True，否则让循环播放并False在函数结束时返回。

您停止了dfs()仅在板上找到第一个字母的点开始搜索的功能word——我已经重新创建了它。我在您的代码中看到的问题：您deepcopy()太早了，您的许多副本从未被使用过；你对xand的使用y令人困惑，如果不倒置，我切换到row和column以下；None你在两个地方用字母替换，dfs()但应该只在一个地方做。

我对您的代码的返工：

from copy import deepcopy

board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
]

def dfs(current, board, word):
    if not word:
        return True

    current_row, current_column = current
    rows, columns = len(board), len(board[0])
    first, rest = word[0], word[1:]

    for r, c in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        row = current_row + r
        column = current_column + c

        if not (0 <= row < rows and 0 <= column < columns):
            continue

        if board[row][column] == first:
            clone = deepcopy(board)
            clone[row][column] = None

            if dfs((row, column), clone, rest):
                return True

    return False

def search_starting_letter(board, word):
    rows, columns = len(board), len(board[0])

    for row in range(rows):
        for column in range(columns):
            if board[row][column] == word[0]:
                clone = deepcopy(board)
                clone[row][column] = None

                if dfs((row, column), clone, word[1:]):
                    return True

    return False

word = "ABCCED"

print(search_starting_letter(board, word))

推荐阅读