Leetcode腐烂橘子问题递归深度超限错误原因咨询

云原生阿岚

2026-8-20

递归深度超限错误原因分析

问题背景

我为LeetCode的《腐烂的橘子》问题写了递归解法，但遇到了Max Recursion Depth Error（最大递归深度错误），就算是grid = [[2,1,1], [1,1,0], [0,1,1]]这种简单输入也会报错，错误出在判断语句行：if ((r,c,time) in seen or r < 0 or c < 0 or r >= R or c >= C or grid[r][c] == 0):。我不需要解题思路，就想搞清楚为啥递归会出这种严重问题。

代码实现

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

递归深度超限的核心原因

无限递归循环无法终止：你的终止条件依赖(r,c,time)是否在seen中，但每次递归time都会加1，导致同一个坐标(r,c)会带着不同的time值被反复处理。比如从(0,0)递归到(0,1)，再从(0,1)递归回(0,0)时，time已经增加了2，(0,0,2)不在之前存入的(0,0,0)里，所以不会触发终止返回，直接陷入无限递归。
多腐烂橘子的递归路径交叉加重问题：每个腐烂橘子都启动一次递归，不同烂橘子的递归路径相互交叉，进一步增加了重复递归的次数，让递归深度迅速超过Python默认的递归深度限制（默认是1000）。
终止条件逻辑存在漏洞：seen集合存储的是(r,c,time)三元组，但同一个坐标的不同time值会被视为不同元素，根本无法有效阻止同一坐标被反复访问，递归没有真正的停止边界。