背景

在计算科学中有一个著名的例子，斐波那契数列（fabnacci）序列，它是考察我们递归思想的运用。

我们简单描述一下，F(n)满足下面的条件：

当n=0时F(n)=0

当n=1时F(n)=1

当n>1时，F(n)=F(n-1)+F(n-2).

示例，F(n)的数组从0.....n

0，1，1，2，3，5，8，13，21，34，55，89，144，。。。。

那么如何实现呢？我们来看一下

java实现

1.两层递归

最简单的一种实现：

 public static long fibonacci(int n){
 if(n==0) return 0;
 else if(n==1) return 1;
 else
 return fibonacci(n-1)+fibonacci(n-2);
 }

问题是：随着n的数值逐渐增多，时间和空间耗费太大，读者可以自行实验。在我的机器上n=50时就不能忍受了。

2.一层递归

考虑优化方式

 public static void main(String[] args) {
 long tmp=0;
 // TODO Auto-generated method stub
 int n=10;
 Long start=System.currentTimeMillis();
 for(int i=0;i<n;i++){
 System.out.print(fibonacci(i)+" ");
 }
 System.out.println("-------------------------");
 System.out.println("耗时："+(System.currentTimeMillis()-start));
 }

public static long fibonacci(int n) {
 long result = 0;
 if (n == 0) {
 result = 0;
 } else if (n == 1) {
 result = 1;
 tmp=result;
 } else {
 result = tmp+fibonacci(n - 2);
 tmp=result;
 }
 return result;
 }

递归时间减少了到不到50%

3.不使用递归

最好的方式，不使用递归的方式来做。

 public static long fibonacci(int n){
 long before=0,behind=0;
 long result=0;
 for(int i=0;i<n;i++){
 if(i==0){
 result=0;
 before=0;
 behind=0;
 }
 else if(i==1){
 result=1;
 before=0;
 behind=result;
 }else{
 result=before+behind;
 before=behind;
 behind=result;

 }
 }
 return result;
 }

小结

面试官可以通过这个题目考察：1.是否熟悉基本的递归实现，递归思想在计算机科学属于最基本的思想。2：是否有优化的思路，通过时间和空间复杂度的转换来减少递归的次数。3：最终是否实现无递归来大大提升运算效率。