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

递归法是一种通过函数自身调用来解决问题的技术。对于小明上楼梯的问题，我们可以定义一个递归函数`countWays(n)`，它表示到达第n个台阶的不同方法数。如果n小于等于0，那么小明不可能到达这个台阶，方法数为0；如果n正好是3的倍数，说明小明可以一步直接上去，所以方法数就是前一个台阶的方法数加1；否则，小明需要选择前3个连续的台阶来上，所以方法数是前3个台阶的方法数之和。

以下是递归法的Python代码：

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

# 测试
stair_count = 15
print("上", stair_count, "阶楼梯的不同方法数:", countWaysRecursive(stair_count))

而递推法则更倾向于循环而非递归，我们从最小的情况开始，逐步构建到更大的情况。下面是利用动态规划思想的非递归版本：

def countWaysIterative(n):
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2  # 初始化前三步的方法数

    for i in range(3, n + 1):
        dp[i] = dp[i - 3]  # 可以分三步走，加上这种情况的数量

    return dp[n]

# 测试
stair_count = 15
print("上", stair_count, "阶楼梯的不同方法数:", countWaysIterative(stair_count))