007_1 斐波那契数列的非递归解法

斐波那契数列的非递归解法

1. 递归解法

public class Demo06 {
    public static void main(String[] args) {
        System.out.println(Fibonacci(6));
    }
    public static int Fibonacci(int n) {
        if(n==1 || n==2)
            return 1;
        else
            return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

2. 非递归解法（自己思路,牛客网通过）

由于使用递归解法进行了许多重复的计算，比如：计算f(10)，要先计算f(9)和f(8)，计算f(9)，要先计算f(8)和f(7)。仅仅这两步f(8)就被计算了2次。当计算f(100)时，使用递归法求解耗时非常严重，主要是因为进行了大量的重复计算。

思想：从下往上计算，先计算f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)，以此类推，算出第n项。

public class Solution {
    public int Fibonacci(int n) {
        if(n==0)
            return 0;
        if(n==1 || n==2)
            return 1;
        
        // 非递归的解法
        int first = 1, second = 1;
        int temp;
        for (int i = 2; i < n; i++)
        {
            temp = second;
            second += first;
            first = temp;
        }
        return second;
    }
}