Python递归实现pascal函数返回帕斯卡三角第n行报错如何解决

问题根因 #

• 第一版报错核心是递归返回值类型不统一：
  • n=1时返回二维列表[[1]]
  • n>1时返回一维列表row
    当n≥3时，pascal(n-1)返回的是一维列表，取result[-1]得到的是整数，调用len()触发类型错误。
• 第二版统一返回完整帕斯卡三角的二维列表，因此需要额外取[-1]才能得到目标行。

调整方案 #

方案1：轻量递归（仅返回目标行，不存储完整三角） #

直接调整递归逻辑，每一层递归都直接返回当前层级的行，空间效率更高：

def pascal(n):
    # 递归终止条件：第1行直接返回[1]
    if n == 1:
        return [1]
    # 获取上一行结果
    last_row = pascal(n-1)
    # 计算当前行
    curr_row = [1]
    for i in range(len(last_row) - 1):
        curr_row.append(last_row[i] + last_row[i+1])
    curr_row.append(1)
    return curr_row

方案2：最小改动（基于第二版代码修改） #

如果需要保留完整三角的存储逻辑，仅修改返回值即可：

def pascal(n):
    if n == 1: 
        return [[1]]
    result = pascal(n-1)
    row = [1]
    last_row = result[-1]
    for i in range(len(last_row)-1):
        row.append(last_row[i]+last_row[i+1])
    row += [1]
    result.append(row)
    # 直接返回最后一行
    return result[-1]

验证效果 #

两种方案调用pascal(3)都会直接返回[1, 3, 3, 1]，符合需求。

内容的提问来源于stack exchange，提问作者Guy