我是小小强，这是我的第4篇原创文章，阅读需要大约10分钟。

题目

描述

查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和1 。
第 i 个数是第i-1个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例

给定 1，返回0
给定 2，返回1
给定10，返回 34

实现

递归实现

java代码

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

结果分析
结果：结果不尽人意，速度非常慢，甚至没有通过 LintCode 的评测。
分析：这种递归不同于一般的递归，在n较大时，两次递归调用中存在大量的重复运算，导致速度非常慢。

非递归实现

java代码

class Solution {
    public int fibonacci(int n) {
        if(1==n)
            return 0;
        if(2==n)
            return 1;
        int a=0;
        int b=1;
        int sum=0;
        while(n>2)
        {
            sum=a+b;
            a=b;
            b=sum;
            n--;
        }
        return sum;
    }
}