1.一只顽猴在一座有n级台阶的小山上爬山跳跃。上山时需从山脚至山顶往上跳n级台阶， 一步可跳1级， 或跳2级，或跳3级， 求上山有多少种不同的跳法? (递归思想)

这是一个典型的递归问题。要计算一只顽猴在有n级台阶的山上跳跃的不同方式数量，我们可以基于以下思路：

1. 如果n为0或1，那么只有一种跳法，即直接到达或直接跳到第一级。
2. 如果n为2，有两种跳法：一次跳两级或分两次，每次跳一级。
3. 如果n为3，有四种跳法：一次跳三级，或跳一级后跳两级，或先跳两级再跳一级，或分三次各跳一级。
4. 对于n>3的情况，到达第n级台阶的方式可以由到达第(n-1)级台阶跳一级、到达第(n-2)级台阶跳两级，以及到达第(n-3)级台阶跳三级这三种情况累加得到。

递归式可以表示为：
F(n) = F(n-1) + F(n-2) + F(n-3)

其中，F(n)表示爬到第n级台阶的不同方式数。

以下是递归函数的基本形式（伪代码）：

FUNCTION countWays(n)
    IF n == 0 OR n == 1 THEN
        RETURN 1
    ELSE IF n == 2 THEN
        RETURN 2
    ELSE IF n == 3 THEN
        RETURN 4
    ELSE
        RETURN countWays(n-1) + countWays(n-2) + countWays(n-3)
    END IF
END FUNCTION

注意：这种递归方法的时间复杂度很高，因为它会重复计算很多子问题。在实际应用中，可以使用动态规划（DP）或记忆化递归来优化性能。

相关问题

用Python算法实现1.一只顽猴在一座有n级台阶的小山上爬山跳跃。上山时需从山脚至山顶往上跳n级台阶， 一步可跳1级， 或跳2级，或跳3级， 求上山有多少种不同的跳法? (递归思想)

要使用递归思想来计算顽猴上山的不同跳法，我们可以定义一个函数，该函数接受当前所在台阶的位置和目标台阶数作为参数。对于当前所在台阶，顽猴可以从该台阶跳1级、2级或3级到达下一级台阶。因此，到达目标台阶的跳法总数应该是到达目标台阶前第1级台阶、前第2级台阶和前第3级台阶跳法数的总和。

这里是一个递归函数的实现方法：

def count_ways_to_climb(n):
    # 如果台阶数小于1，则只有一种跳法，即不跳
    if n < 1:
        return 0
    # 如果台阶数为1，只有一种跳法，即跳1级
    elif n == 1:
        return 1
    # 如果台阶数为2，有两种跳法，即跳1级然后跳1级，或者直接跳2级
    elif n == 2:
        return 2
    # 如果台阶数为3，有四种跳法，即跳1级然后跳2级，跳2级然后跳1级，
    # 直接跳1级再跳1级最后跳1级，或者直接跳3级
    elif n == 3:
        return 4
    # 对于大于3的情况，使用递归计算跳法
    else:
        return count_ways_to_climb(n-1) + count_ways_to_climb(n-2) + count_ways_to_climb(n-3)

# 示例：计算有5级台阶的跳法数
print(count_ways_to_climb(5))

这个函数首先处理了基本情况，即台阶数小于1时没有跳法，台阶数为1、2、3时有固定数量的跳法。然后对于大于3的情况，递归地调用自身来计算到达前一级、前两级和前三级台阶的跳法数，并将它们相加得到当前台阶的跳法总数。

猴子爬山一只顽猴在一座有50级台阶的小山上爬山跳跃。上山时需从山脚至山顶往上跳50级台阶，一步可跳1级，或跳2级，或跳3级，求上山有多少种不同的跳法？ （请用递归和递推方法分别实现，并比较两者的运行效率）

这个问题是一个经典的动态规划问题，可以使用递归和递推两种方法解决。

**递归解法**：
设f(n)表示到达第n级台阶的不同跳法数，递归规则如下：
- 如果n=1，只有1种方法（直接跳一级），f(1)=1；
- 否则，f(n) = f(n-1) + f(n-2) + f(n-3)，因为可以从前一级、前两级或前三级跳到第n级。

递归函数表达式如下：

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

递归方法虽然直观，但由于重复计算较多，效率较低，时间复杂度大约为O(4^n)。

**递推解法**（也叫记忆化搜索或自底向上策略）：
我们可以创建一个大小为n+1的数组dp[n]，其中dp[i]表示到达第i级台阶的不同跳法数。这种方法避免了重复计算，提高了效率。

def dynamic_programming_ways(n):
    dp = [0] * (n + 1)
    dp[1], dp[2], dp[3] = 1, 1, 1  # 初始化基础情况

    for i in range(4, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    return dp[n]

递推方法的时间复杂度为O(n)，因为它只需要遍历一次数组。

**运行效率比较**：
递归方法在每次递归调用时都会进行相同的计算，造成大量冗余，而递推方法通过预先存储中间结果，避免了这种重复，因此在处理大规模数据时，递推方法会更快更有效率。对于小规模的问题，两者差距不大；但对于大型问题，递推方法的优势就很明显了。