楼梯问题：不同场景下的递归基准情况差异探究

第一种问题变体 #

有n级楼梯，人从底部出发，每次可爬1或2级，求到达顶部的路径数。它的基准条件代码如下：

if(n <= 1) return n;

这个逻辑很直观：1级楼梯仅1种走法（直接爬1级）；0级楼梯也对应1种走法（无需动作就已在顶部）。

第二种问题变体 #

有n级楼梯，人从底部出发，每次可爬1、2或3级，求到达顶部的路径数。它的基准条件代码如下：

if(n < 0)
    return 0;

if(n == 0)
    return 1;

为什么0级楼梯对应1种走法？ #

这是递归逻辑里的空操作约定：当n=0时，说明已经刚好到达顶部，不需要做任何动作，这种“什么都不做”的状态就对应1种有效路径。这个约定是为了让递归拆分逻辑自洽——比如计算n=3的路径数时，会拆分成“爬1级后剩2级”“爬2级后剩1级”“爬3级后剩0级”，最后一种情况刚好到达，所以要算1种路径，这样递归结果才会正确。

为什么后者要显式处理n<0的情况，而前者不需要？ #

前者的递归逻辑里，每次只减1或2，当n<=1时就触发基准条件返回，不会出现n<0的情况：

• 当n=1时，拆分后是“爬1级剩0级”，直接返回1；
• 当n=2时，拆分成“爬1级剩1级”和“爬2级剩0级”，都不会出现负数。

但后者每次可以减3，比如当n=2时，拆分出“爬3级剩-1级”，这种情况意味着不可能的路径（没法爬3级去到达只有2级的楼梯顶部），所以要返回0，排除这种无效情况。

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