Java递归算法经典实例（经典兔子问题）

Java递归算法经典实例——经典兔子问题，是一种常见的递归求解问题。其实，兔子问题可以通俗的解释成：一对小兔子出生后第三个月开始，每个月都可以生一对小兔，假设每对兔子都能一直生育下去，那么 n 个月后共有多少对兔子。

这个问题的解法可以使用递归算法进行求解。将 f(n) 表示第 n 个月的兔子对数，则 f(n) 的值等于 (n-1) 月兔子对数加上 (n-2) 月兔子对数。根据此递推公式可以编写以下递归函数：

public static int rabbit(int n) {
    if(n == 1 || n == 2) {
        return 1;
    } else {
        return rabbit(n - 1) + rabbit(n - 2);
    }
}

这是一种非常经典的递归写法，但是当 n 过大时，这个递归函数的效率会非常低下，会出现递归层级过深、重复计算等问题。

为了避免这些问题，我们可以使用非递归的方法进行求解。具体来说，可以使用一个数组进行数据的存储，当计算 f(n) 时先预先计算出之前的 f(1) ~ f(n-1) 的值，然后使用这些值进行递推计算 f(n) 的值。以下是使用非递归方法的代码示例：

public static int rabbit(int n) {
    if(n == 1 || n == 2) {
        return 1;
    }
    int[] arr = new int[n];
    arr[0] = arr[1] = 1;
    for(int i = 2; i < n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n - 1];
}

以上是两种不同的解决方案，前者是递归方法，比较容易理解，但是当数据过大时会出现效率问题。后者是非递归方法，使用数组存储数据，虽然可能不太好理解，但是其效率较高，更加实用。在实际开发中，根据具体情况选择合适的算法实现是非常重要的。