递归算法（一）

用递归计算斐波那契数列，那么什么是斐波那契数列呢？这里引用百度百科的定义：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：

F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

代码如下：

    public class Test01 {

        public static void main(String[] args) {

            System.out.println(f(8));

        }

        public static int f(int n) {

            if(n<=2) {

                return 1;

            }

            return f(n-2)+f(n-1);

        }

    }

用递归计算数，需要注意关键的三点。第一，必须有跳出的条件，否则会导致内存溢出，比如上面的代码找到了第8项，递归回调8次就跳出来了；第二，必须给初始值赋值，否则无法计算出数；

第三，需要推导出要计算的表达式。用递归计算斐波那契数列的表达式的规律为，前两项的加起来等于第三项，用数学表达式即为：F(n)=F(n - 1)+F(n - 2)