用python完成： 小明上楼帶，最多一步4阶。从帷盘输入一个整数n，分别用递推幗和递归幗计算小明幘n阶楼帶的幘幗数帺

小明上n阶楼梯，如果一步最多可以上4个台阶，可以通过递推法和递归法来计算上楼的方法数。

1. 递推法：递推法是一种动态规划算法，可以通过已知的较小问题的解来构建较大问题的解。对于上n阶楼梯的问题，可以定义一个数组dp，其中dp[i]表示上到第i个台阶的方法数。递推关系为dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]，因为小明最后一步可以是1到4个台阶。

def climbStairs(n):
    if n == 1: return 1
    dp = [0] * (n+1)
    dp[1], dp[2], dp[3], dp[4] = 1, 2, 4, 7
    for i in range(5, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]
    return dp[n]

2. 递归法：递归法通过函数自己调用自己来解决问题。对于上n阶楼梯，递归函数可以定义为climbStairsRecur(n)，其中n是当前台阶数。递归的基本情况是当n小于等于1时，方法数为1。递归公式与递推法相同。

def climbStairsRecur(n):
    if n <= 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    return climbStairsRecur(n-1) + climbStairsRecur(n-2) + climbStairsRecur(n-3) + climbStairsRecur(n-4)

在实际应用中，递推法由于其空间效率通常优于递归法，因为递归法可能会产生大量的重复计算。然而，递归法在理解上更为直观。78