斐波那契数列的两种解题思路：递归VS迭代

一、问题描述

要求输入一个整数n，请你输出斐波那契数列的第n项

二、算法分析

给出一系列斐波拉契数列：0 1 1 3 5 8 13 21 。。。

通过观察，很容易发现：

         1     n=0,1

f(n)   =         f(n-1)+f(n-2)  n>1

三、算法设计

递归法：根据递归公式实现递归函数

缺点：递归过程中会包含很多重复的运算，所以效率不高

迭代法：迭代的思想就是不断地用变量的旧值递推新值的过程。迭代法相对于递归效率要高，因为节省了重复计算

四、编码实现

（1）递归法

public int Fibonacci(int n) {
			if(n<=1) 
	            return n;
	        else
	        	return Fibonacci(n-1)+Fibonacci(n-2);
	 }
           

（2）迭代法

public int Fibonacci1(int n){
		int f0 = 0;
		int f1 = 1;
		int currentNum=0;
		if(n<=1){
			return n; 
		}
		for(int i=2; i<=n;i++){
			currentNum = f0 + f1;
			f0 = f1;
			f1 = currentNum;
		}
		return currentNum;
	 }