Python递归函数中何时需要预先声明列表?结合矩阵路径、楼梯路径代码分析
问题核心原因
你遇到的报错和递归特性没有关联,本质是Python函数内的变量必须先完成赋值才能使用,和变量是不是列表类型无关。
两段代码的差异分析
- 矩阵路径代码报错原因
hpaths、vpaths两个变量仅在对应if条件成立时才会被赋值:
- 当递归走到最右列时,
c == dc,if c<dc判断不成立,hpaths从未被创建,后续遍历hpaths时就会触发UnboundLocalError - 当递归走到最下行时,
r == dr,if r<dr判断不成立,vpaths从未被创建,后续遍历vpaths也会触发报错
- 楼梯路径代码正常运行原因
paths1、paths2、paths3三个变量没有放在条件分支内,只要函数没有走到前面的return分支,这三个变量一定会被赋值:
即使传入负参数的递归调用返回空列表,变量本身依然是有确定值的,不会出现未定义的情况。
什么时候需要预先初始化列表变量
只有满足以下两个条件时,你需要预先给列表变量赋初始值(通常是空列表[]):
- 变量的赋值逻辑写在条件分支内
- 无法保证所有执行路径都会触发该条件分支的执行
如果变量的赋值逻辑在所有非return的执行路径下都会被执行,就不需要提前声明。
修正后的矩阵路径代码示例
# GET MATRIX PATH (0,0-->3,3) dr-> destination row, dc-> destination column def gmp(r,c,dr,dc): # base case if r==dr and c==dc: return [""] # 提前初始化空列表,避免分支不执行时变量未定义 hpaths = [] vpaths = [] if c<dc: hpaths=gmp(r,c+1,dr,dc) if r<dr: vpaths=gmp(r+1,c,dr,dc) gmp_res=[] for path in hpaths: gmp_res.append("h"+path) for path in vpaths: gmp_res.append("v"+path) return gmp_res print(gmp(0,0,3,3))
内容的提问来源于stack exchange,提问作者smor
相关产品推荐
相关产品推荐

