（程序题）假设一段楼梯共15个台阶，小明一步最多能上3个台阶。编写程序计算小明上这段楼梯一共有多少种方法。要求给出递推法和递归法两种代码。Python 3.x

这是一个经典的动态规划问题，可以用递推法（bottom-up approach）和递归法（top-down approach）解决。

**递推法（Python）**：

def climb_stairs_recursion(steps, max_step):
    if steps <= max_step:
        return 1
    else:
        ways = 0
        for i in range(1, min(steps // max_step + 1, max_step) + 1):  # 分别考虑上1步、2步...直到最大步数
            ways += climb_stairs_recursion(steps - i * max_step, max_step)  # 余下的台阶数不变
        return ways

steps = 15
max_step = 3
print("Total ways:", climb_stairs_recursion(steps, max_step))

**递归法（Python）**：

def climb_stairs_recursion_dp(steps):
    dp = [0] * (steps + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2  # 特殊情况：走2步直接到达

    for i in range(3, steps + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]  # 三步并一步的情况

    return dp[steps]

steps = 15
print("Total ways:", climb_stairs_recursion_dp(steps))

这两种方法最终都会得到相同的答案，即小明上完15级台阶的不同走法总数。