斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368......
我记得在初学C语言的时候，大学老师经常会讲一些常见的数学问题及递归的使用，其中斐波那契数列就是一定会被拿出来举例的。在后来工作中，面试做面试题的时候，也很大概率会出现编写算法实现斐波那契额数列求值。可以说，在我们编程道路上，编写算法实现斐波那契数列是每个程序员必定会做的一件事。昨天去参加腾讯课堂举办的一个线下活动，活动中有一位嘉宾，是某课堂的创始人，也是算法课程的讲师，就讲到了这个问题，算是颠覆了我对该问题的认知。本文就根据这名讲师的讲解，来分析和整理一下该问题算法的实现。
下面，我们来看看其中几种常见的算法，并分析其效率。
1、递归法
通过观察，我们会发现其中的规律，第一项和第二项的值均为1，后面每项的值都是前两项值之和，所以我们很多人基本上都会使用递归来实现，常见的算法如下：
1 public int fib(int n) { 2 if (n == 1 || n == 2) { 3 return 1; 4 } 5 return fib(n - 2) + fib(n - 1); 6 }