一、前言斐波那契数列是指这样数列1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、55
学习递归时最先使用的简单例子是斐波那契数列，当时也惊叹于递归的魔力。 后来，在一次面试过程中，面试官提出了这个问题。 我想了想为什么这么简单。 当面试官让我在测试用例中输入100的时候，我发现我还太年轻了…我一直觉得没有问题的简洁优雅的算法，花了这么长时间，也不实用。
1publicintfib(intn ) 2if ) n==1||n==2) {3 return 1； 4}5returnfib(n-2 ) fib ) n-1 )； 6 )可以看到，f(n )这个方法被多次调用，进行了多次重复计算。 其时间复杂度为o(2^n )，呈指数级，其空间复杂度为o ) n )。
二、正文1、动态规划法：将计算出的数据保存在一个数组中，需要最终值时直接从数组中提取即可，避免重复计算。 存在时间复杂度为o(n )的for循环，打开长度为n的数组，因此空间复杂度也为o ) n )
1publicintfib(intn ) {2 int[] fib=new int[n]； 3 fib[0]=1； 4 fib[1]=1； 5for(intI=2； i n； I ) {6 fib[i]=fib[i - 2] fib[i - 1]； 7 }8 return fib[n - 1]； 9 ) 2、迭代法：尽管上述算法已经很有效率，但仍能找到一个问题。 实际上在整个数组中，每次计算都只需要最新的3个值，之前的值计算结束后就不再需要了。 也可以用三个变量保存数据。 时间复杂度仍然是o(n )，空间复杂度为3级常数，即空间复杂度为0
1publicintfib(intn ) { 2 int first=1； 3 int second=1； 4 int third=2； 5for(intI=3； i=n； I ) { 6 third=first second； 7第一次=第二次； 8 second=third； 9 }10 return third； 11 u 3，末尾递归法)用两个变量保存计算值，传递给下一个计算。 递归过程中也根据n值的变化依次反复运算。 和循环一样，时间复杂度和空间复杂度也一样，但比循环简洁优雅
1公共int fib (intn，int first，int second ) 2if ) n=1) {3 return first； 4 ) else {5}返回fib (n-1，second，first second )； )7) 4、公式法：求斐波那契数列值有一个公式…
1公共int fib (intn )2doublec=math.sqrt ) 5； 3return(int ) ) math.pow ) (1c )/2，n )-math.pow )-c )/2，n ) )/c )； 4 )三、总结其实递归算法所花的时间和空间都非常大，所以通过一定的手段对其进行优化，并且算法也并不是越短越好。 我们更应该追求的是效率，好的算法要兼顾效率和简洁，需要不断思考和磨练…共勉！