递归算法求解一个古典的兔子问题

从今天起，开始研究java的相关算法，如果大家有什么好的算法题目的话，麻烦推荐一下，大家一起学习，一起研究，谢谢！如果有什么好的算法题目，我也会在解答后发表上来，有什么不足或者错误大家可以批评指正，或者提出自己的见解，谢谢！

 

下面是java经典算法里面的32题整理，按照自己的思维一步步来进行解析和说明，也希望给一些没有思路的朋友提供下思路，当然如果大家有什么好的思路的话也可以提出来。

 

【程序1】 题目：古典问题：3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

分析：首先我们要明白题目的意思指的是每个月的兔子总数(这里应该是按对来计算的)；我们假设将兔子分为小中大三种，兔子从出生后每三个月就生出一对兔子，那么我们假定第一个月为小兔子，第二个月为中兔子，第三个月之后就为老兔子(老兔子每过三个月还会再生的)，那么第一个月分别有1、0、0，第二个月分别为0、1、0，第三个月分别为1、0、1，第四个月分别为,1、1、1，第五个月分别为2、1、2，第六个月分别为3、2、3，第七个月分别为5、3、5……

兔子总数分别为：1、1、2、3、5、8、13……

 

于是得出了一个规律，从第三个月起，后面的兔子总数都等于前面两个月的兔子总数之和。

 

于是有了下面的编程：

 

public class TestOne {

	public static void main(String[] args) {
		int rabbitNum = 1;
		for(int i = 1 ; i < 20 ; i++){
			rabbitNum = getMonthNum(i);
			System.out.println("兔子第   "+i+"  个月的总数为："+rabbitNum);
		}
		
	}
	
	public static int getMonthNum(int x){
		int initRabbit = 1;
		
		if(x == 1 || x == 2){
			return initRabbit;
		}
		
		initRabbit = getMonthNum(x-1) + getMonthNum(x-2);
		
		return initRabbit;
	}
}

 

 

 

 

在这个例子中，主要用到了递归的思想。学过java的人一般都学过递归。递归函数提供了不一样的思维方式，用他来解决往往程序要短小很多，思维也会很清晰。它很适合解决树中的一些问题，在编译原理中也可以经常看到。

它的主要的解决问题的思维是这样的：

先解决最基础的简单的问题；

然后把复杂的问题归结为较简单的问题或把较大的问题分解为较小的问题。

下面这小段程序是用递归写的用来求1到n所有这些正整数的和的：

public static int f(int n){
    if(n==1) return 1;
     return n+f(n-1);
}

 

 

 

 

第一句解决了最简单的问题，就是n==1的情况。接下去在求较复杂的f（n）的时候把它归结为较简单的问题f（n-1）。

用递归也有几个需要注意的问题：

1.程序总得要有机会让它退出来，不然会变成死循环。就象这里的第一句，而且一般来说位置也通常在第一句。

2.递归还有性能开销。一是因为函数调用时参数的入栈出栈操作。二是有些问题处理不当会出现重复计算（不是很老到的程序员经常会出这样的问题，导致性能有问题，然后说递归根本没实际意义）。