递归函数中的返回冲突

Question

我正在写一个函数来解word search problem。然而，我遇到了一个困境，即如何正确地从dfs递归函数中获取返回值。问题是：如果我在代码的最后一行使用关键字return，那么一旦返回被命中，它就会过早地结束for direction in [[0,1],[0,-1],[1,0],[-1,0]]循环。但是，如果我删除最后一行中的return，递归函数将正常工作，但它永远不会从中返回Trueif 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

Answer 1

@kszl给您的建议是好的，检查递归调用的结果，只有当它是True时才返回，否则让循环播放并在函数末尾返回False

您取消了只在电路板中找到word的第一个字母的点上启动dfs()搜索的函数，我重新创建了该函数。我在代码中看到的问题：你deepcopy()太早就进入了董事会，你的许多副本从未被使用过；你对x和y的使用令人困惑，如果没有颠倒，我切换到下面的row和column；在dfs()中的两个位置用None替换字母，但只能在一个位置替换

我对您的代码进行的返工：

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))