用递归方法求解爬楼梯问题

Question

一步最多能上3个台阶，一共15个台阶，通过递归计算，共有几种方法？

def climbstairs(n):
    if n == 1:
        way = 1
    elif n == 2:
        way = 2
    elif n == 3:
        way = 4
    else:
        way = climbstairs(n-1) + climbstairs(n-2) + climbstairs(n-3)
    return way
n = int(input("请输入台阶的总数："))
num = climbstairs(n)
print(f"爬{n}阶台阶一共有{num}种方法")

前12都对，台阶数变成13之后就开始出错，到底哪里写错了啊？

Answer 1

def count_ways_to_climb_stairs(n):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    else:
        return count_ways_to_climb_stairs(n - 1) + count_ways_to_climb_stairs(n - 2) + count_ways_to_climb_stairs(n - 3)

total_ways = count_ways_to_climb_stairs(15)
print("一共有", total_ways, "种方法可以爬上15个台阶")