CODEWITHSUNDEEP
pythonrecursionreturn
Albert G Lieu
Albert G Lieu

Reputation: 911

return conflicts in recursive function

I am writing a function to solve the word search problem. However, I run into a predicament of how to correctly get return value from my dfs recursive function. Here is the problem: if I use the keyword return in the last line of the code, it prematurely ends for direction in [[0,1],[0,-1],[1,0],[-1,0]] loop once the return is hit. However, if I remove the return in the last line, the recursive function will work fines, but it will never return True from if len(word)==0:print("TRUE") return True statement even when the statement is met. I basically understand that once the program hits return it will ignore all codes after it. Could you please explain how to get out of this trap? 

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

Upvotes: 0

Views: 76

Answers (1)

cdlane
cdlane

Reputation: 41872

The advice that @kszl is giving you is good, check the result of the recursive call and only return if it's True, otherwise let the loop play out and return False at the end of your function.

You left off your function that starts the dfs() search only at points in the board where the first letter of the word is found -- I've recreated that. Issues I see with your code: you deepcopy() the board too early, many of your copies never get used; your use of x and y are confusing, if not inverted, I switched to row and column below; you replace letters with None in two places in dfs() but should only do it in one.

My rework of your code:

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

Upvotes: 1

Related Questions