摘要：斐波那契数列是一个古老而有趣的问题，兔子繁殖问题是它最经典的问题之一，通过斐波那契数列递归运算便可以解决兔子繁殖问题的分析求解运算。本文在对递归与非递归求斐波那契数列兔子问题进行了详细说明。
关键词：斐波那契数列兔子问题、递归与非递归运算
1 引言
斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，在数学上，斐波纳契数列以如下被以递推的方法定义：F（1）=1，F（2）=1，F（n）=F（n-1）+F（n-2）（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。
递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归，同样斐波那契兔子问题也可以通过递归运算进行解决。递归运算是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。而对于兔子繁殖问题的分析，非递归算法也存在一定的便利性。
由于斐波那契数列数列是以兔子的繁殖引入的，因此也叫“兔子数列”。它指的是这样一个数列：0，1，1，2，3，5，8，13......从这组数可以很明显看出这样一个规律：从第三个数开始，后边一个数一定是在其之前两个数的和。这就是斐波那契数列。
2 斐波那契数列兔子问题
斐波那契的名字与一个无穷的数列联系在了一起，这个数列用来解决《算经》中提到的一个有趣的“兔子繁殖问题”：如果每对兔子每月能繁殖一对子兔，而子兔在出生后第二个月就有了生殖能力，第三个月就生产一对兔子，以后每个月生产一对。假定每对兔子都是一雌一雄。试问一对兔子一年能繁殖多少兔子？
第一个月有一对兔子；
第二个月兔子长大了，但还是只有一对兔子；
第三个月多了一对幼年兔子，共有两对兔子了；
第四个月又生了一对幼年兔子，同时第三个月的幼年兔子长成了成年兔子；
……
那么兔子数量的规律即：1，1，2，3，5，8，13，21……
分析计算：
设f（n）表示第n个月所有的兔子总数。
F（1）=1，f（2）=1，f（n）=f（n-1）+f（n-2）。
第n个月的兔子总数来源于两个方面，一是第n-1个月原来就有的兔子总数，即f（n-1），二是新出生的兔子总数。由于新出生的兔子在出生的那一月的下一个月的再下一个月开始每个月生新兔子，我们可以假设兔子分为小兔子，中兔子和大兔子，小兔子过一月变为中兔子，中兔子过一月变为大兔子，大兔子每个月生小兔子。我们要算第n个月所有的新出生的小兔子的个数，也就是第n月所有的大兔子总数，这个个数等于第n-1个月所有中兔子和大兔子的总数（因为第n-1个月的中和大兔子第n个月长成了大兔子，第n个月的小兔子完全来源于第n-1个月的中和大兔子），同理，第n-1月所有的中和大兔子又完全来源于第n-2月所有的小，中和大兔子，即第n-2月的所有兔子，即F（n-2）。故f（n）=f（n-1）+f（n-2）。由以上的规律我们可以得到：
第0个月 1
第1个月 1
第2个月 2（第0个月的兔子可以生产，（1*2））
第3个月 3（第1个月的兔子可以生产，（1*2+2-1））
第4个月 5（第2个月的兔子可以生产，（2*2+3-2））
第5个月 8（第2个月的兔子可以生产，（3*2+5-3））
那么递归求斐波那契兔子问题的代码：
import java.util.Scanner；
public class Main
{
public static void main（String[]args）{
System.out.print（"请输入月份："）；
int n = new Scanner（System.in）.nextInt（）；
System.out.println（"兔子的对数为：" + getNums（n））；
}
public static int getNums（int n）
{
if（n <= 1）return n；
return getNums（n - 1）+ getNums（n - 2）；
}
}
如果使用非递归解决斐波那契兔子繁殖问题，那我们需要开辟一块数据，来存储我们“前面月份”得到的数量。我们使用 动态规划 的思想，即我们需要求解第 N 个月的兔子数量，依赖于求解第 N-1 个月和第 N-2 个月的兔子数量这两个子问题，我们可以自底向上的求解出每个子问题的解，并保存起来，然后最终求解第 N 个月的兔子数量时直接使用已知的子问题的解即可。代码如下：
public static int getNums（int n）
{
int[]nums = new int[n + 1]；
nums[1]= 1；// 初始状态：nums[0]= 0，nums[1]= 1
for（int i = 2；i < nums.length；i++）
{
nums[i]= nums[i - 1]+ nums[i - 2]；
}
return nums[n]；
}
我们使用了 nums 这个数组保存了每个月兔子数量的值，其实我们也大可不必这么奢侈，在这个问题中我们其实只需要知道前两个月的情况即可，那么我们可以只创建一个长度为 2 的数组分别保存 N-2 个月和 N-1 个月的情况即可。代码如下：
public static int getNums（int n）
{
if（n <= 1）return n；
// 使用一个长度为 2 的数组存储前两位的值
int[]nums = new int[]{ 0，1 }；
int result = 0；
for（int i = 2；i <= n；i++）{
result = nums[0]+ nums[1]；
nums[0]= nums[1]；
nums[1]= result；
}
return result；
}
3 结论
由以上的递归与非递归的程序运算，我们可以看出两种方法在解决与分析斐波那契的兔子繁殖问题上，存在共同点，但同时也存在不同的地方使用非递归的解法（动态规划），效率上来说也会比递归好很多，不仅仅是因为递归会使得栈的深度变得很大，而且在递归的过程中，在不同的 n 值下，还会产生很多重复的计算。而非递归的方式仅仅只是获取到之前的值使用，不存在重复的计算消耗。
参考文献：
[1]张婧馨.斐波那契数列在优化计算中的应用[J].黑龙江科学，2016（23）：20-22.
[2]周琪，池艳艳，周一勤.N阶斐波那契数列和阶黄金分割及其应用[J]. 浙江交通职业技术学院学报.2016（02）：24-28.
[3]于海杰.奇妙的斐波那契数列[J].赤峰学院学报（自然科学版）.2014（16）：2-4.
[4]贾菲菲.斐波那契数列的研究与应用[J].科技创新与应用.2014（13）：53.
[作者简介]吴月，女，山东协和学院计算机科学与技术专业在读本科生。王红（1982），指导教师，通讯作者，女，硕士，副教授，研究方向：物联网，教育管理。
论文作者:吴月,王红
论文发表刊物:《基层建设》2019年第14期
论文发表时间:2019/7/26
标签：兔子论文; 递归论文; 个月论文; 数列论文; 我们可以论文; 算法论文; 总数论文; 《基层建设》2019年第14期论文;