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

当然可以，为了计算小明上15级台阶的不同方法数，我们可以使用动态规划的思想，包括递推法和递归法。这里我将分别展示这两种方法的Python代码。

**递推法（Bottom-Up Approach）**:

def stair_climb_dp(n, max_steps):
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1  # 初始化前两个状态

    for i in range(2, n + 1):
        for j in range(1, min(i, max_steps) + 1):  # 考虑每一步的可能性
            dp[i] += dp[i - j]  # 如果当前台阶剩余数小于最大步数，则可以选择之前的方案加上这一步

    return dp[n]

steps = 15
max_steps = 3
ways = stair_climb_dp(steps, max_steps)
print(f"小明有 {ways} 种上楼的方式。")

**递归法（Top-Down Approach）**:

def stair_climb_recursion(n, max_steps, memo={}):
    if n == 0 or max_steps == 0:
        return 1  # 基本情况，已到达或没步骤了，只有一种方法
    elif n < 0 or n > max_steps:
        return 0  # 非法情况，返回0

    if (n, max_steps) not in memo:
        memo[n, max_steps] = stair_climb_recursion(n - max_steps, max_steps) + stair_climb_recursion(n - 1, max_steps)

    return memo[n, max_steps]

ways = stair_climb_recursion(steps, max_steps)
print(f"小明有 {ways} 种上楼的方式。")

# 递归可能会导致大量重复计算，所以通常会结合缓存（memoization）来优化