一个顽猴在一座有30级台阶的小山上爬山跳跃。猴子上山一步可跳1级，或跳3级。 试求上山的30级台阶有多少种不同的爬法。用递推和递归分别编码实现？用java

这是一个经典的组合数学问题，可以用动态规划（Dynamic Programming）中的“阶乘排列”（rising factorial）或“三角数”（triangular number）的概念来解决。对于每一步，猴子可以选择上一级或者三级，所以总的爬法数可以通过前一步的爬法数相加得到，初始状态时，只有一步，只有一种方式（一步一级或一步三级）。

以下是递推和递归的Java实现：

**递推实现**（动态规划）：

public class MonkeyJumps {
    public static int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return climbStairs(n - 1) + climbStairs(n - 3); // 上一步1级或3级
        }
    }

    public static void main(String[] args) {
        int steps = 30;
        int ways = climbStairs(steps);
        System.out.println("The monkey has " + ways + " different ways to climb the stairs.");
    }
}

**递归实现**（虽然理论上可行，但会非常慢，因为有大量的重复计算）：

public class RecursiveMonkeyJumps {
    public static int recursiveClimbStairs(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return recursiveClimbStairs(n - 1) + recursiveClimbStairs(n - 3); // 递归调用
        }
    }

    //...其他代码同上...
}

递推版本更高效，因为避免了重复计算，而递归版本时间复杂度较高，不适合大型输入。