Max Recursion Depth Error With Grid Search Problem

Mnifldz 0
Viewed 13

I've written out a potential solution to a Leetcode problem but I get this error involving maximum recursion depth. I'm really unsure what I'm doing wrong. Here's what I've tried writing:

def orangesRotting(grid):
    R,C = len(grid), len(grid[0])
    seen = set()
    min_time = 0
    
    def fresh_search(r,c, time):
        if ((r,c,time) in seen or r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0):
            return
        elif grid[r][c] == 2:
            seen.add((r,c,0))
        elif grid[r][c] == 1:
            seen.add((r,c, time + 1))
        
        fresh_search(r+1,c,time+1)
        fresh_search(r-1,c,time+1)
        fresh_search(r,c+1,time+1)
        fresh_search(r,c-1,time+1)      
    
    for i in range(R):
        for j in range(C):
            if grid[i][j] == 2:
                fresh_search(i,j,0)
                
    for _,_,t in list(seen):
        min_time = max(min_time,t)
    
    return min_time

Even on a simple input like grid = [[2,1,1], [1,1,0], [0,1,1]]. The offending line always appears to be at the if statement

if ((r,c,time) in seen or r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0):

Please note, I'm not looking for help in solving the problem, just understanding why I'm running into this massive recursion issue. For reference, here is the link to the problem. Any help would be appreciated.

recursion
1 Answers

So let's trace through what you are doing here. You iterate through the entire grid and if the value for that cell is 2 you call fresh_search for that cell. We'll start with [0,0]

In fresh_search you then add the cell with times seen = 0 to your set.

Now for all neighboring cells you call fresh_search so we'll just look at r+1. For r+1 your method fresh_search adds the cell to your set with times seen = 1 and then calls fresh_search again with all neighboring cells.

Next we'll just look at r-1 which is our origin and now fresh_search is being called with this cell and times seen = 2. Now this value isn't in the set yet because (0,0,0) != (0,0,2) so it adds it to the set and again calls fresh_search with the r+1 cell but now times seen = 3

and so on and so forth until max recursion.

Amos Baker0
Related