Java 菲波那切数列之递归迭代算法求值

斐波那契数列，又称黄金分割数列，以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、55 、……

`数列从第3项开始，每一项都等于前两项之和。`

求该数列的第N项数值

1.递归方法

递归重要的规则：当满足一定条件时需要终止递归调用。否则陷入调用死循环

此数列当x=1 或 x=2 时可以当做满足跳出递归条件

//x 表示第几个数
f(x)=f(x-1)+f(x-2) 
f(x-1)=f(x-2)+f(x-3)
f(x-2)=f(x-3)+f(x-4)
......
当x-n=1 或 2时 直接返回1

代码如下:

publix static int t1(){ 
if (x == 1 || x == 2) {
    return 1;
}
return t1(x - 1) + t1(x - 2);
}
}

2.迭代方法

如：

1 1 2 3 5 8 m n result=m+n
1 result = m+n = 0+1 可以看做 0 + 1
2 result = m+n = 1+1
3 result= m+n 1+2
5 result =m+n 2+3
8 result = m+ n 3+5
…..

可以看出当前组数m的值是上一组数的n;上一组数的 result 是下一组数的n

即如果result代表当前项的斐波那契数，m代表前两项的，n代表前一项，我们在每一次计算完后将n的值赋给m，
将result的值赋给n，使得我们可以一项一项的算出斐波那契数

publix static int t2(){ 
int m=0;
int n =1;
int result=1;
int count=1;
 //count 1 开始 ，1 时 不进循环 直接返回1
while (count < x) {

    result = m+n;
    m = n;
   n = result;
    count++;

}
return result;
}

运行效率比较：

递归效率慢它会消耗了大量的内存与时间，当参数值过大时，会计算很长的时间

迭代求值效率快

测试：

StopWatch time = new StopWatch();
time.start("t1");
System.out.println(t1(20));
time.stop();
time.start("t2");
System.out.println(t2(20));
time.stop();
System.out.println(time.prettyPrint());