递归爬楼梯问题中如何将递增计数返回给递归栈的下一层调用

现有代码的核心问题 #

• Python 中整数是不可变类型，你将numberOfWays作为参数传入辅助函数，在辅助函数内修改该参数只会修改当前栈帧的参数副本，不会影响外层函数的同名变量
• 辅助函数的递归调用返回值没有被接收和累加，你调用了staircaseTraversalHelper(...)但没有把它的返回值加到总路径数中，相当于计算结果直接被丢弃
• 辅助函数的循环逻辑存在缺陷：只要某一步newHeight == height就直接返回，会中断当前层的循环，漏掉同层其他step对应的合法路径
• 主函数的边界判断错误：即使路径数为0（比如height为0的合法边界场景）也会错误返回-1

修正后的递归解法 #

递归的核心逻辑是将大问题拆解为子问题：到达高度h的路径总数，等于所有「最后一步走1~maxSteps步」对应的前序路径数之和，不需要额外的辅助函数，直接通过返回值传递计算结果即可：

def staircaseTraversal(height, maxSteps):
    # 递归终止条件1：高度为0时，只有1种方法（原地不动）
    if height == 0:
        return 1
    # 递归终止条件2：高度为负时，没有合法走法
    if height < 0:
        return 0
    total_ways = 0
    # 累加所有合法步长对应的子问题解
    for step in range(1, maxSteps + 1):
        total_ways += staircaseTraversal(height - step, maxSteps)
    return total_ways

代入你给出的示例height=3、maxSteps=2，计算结果为3，符合预期。

递归解法优化建议 #

• 设计递归逻辑时优先遵循「子问题返回值聚合得到父问题解」的思路，尽量不要用全局变量、可变对象传值来统计结果，代码可读性和可维护性会更高
• 写递归前先明确终止条件，再梳理父子问题的映射关系，不要先急于写循环逻辑
• 如果输入的height数值较大，当前纯递归实现会有大量重复计算，可以加记忆化缓存优化，示例如下：

from functools import lru_cache

@lru_cache(maxsize=None)
def staircaseTraversal(height, maxSteps):
    if height == 0:
        return 1
    if height < 0:
        return 0
    total_ways = 0
    for step in range(1, maxSteps + 1):
        total_ways += staircaseTraversal(height - step, maxSteps)
    return total_ways

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