遞歸和迴圈:斐波那契數列

題目描述

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。 n<=39

解題思路

遞推公式f(n)=f(n)=
當n=0=0,當n=0 當
n=1=1,當n=1
其他=f(n−1)+f(n−2)看到這大家很容易想起遞歸，課堂上老師講遞歸的時候的經典例子。但是當n很大的時候，就會出現堆棧溢出。堆棧溢出的主要原因是，遞歸重覆的計算太多，很多計算是可以避免的，用迴圈計算結果，顯根據前兩項算出第三項，以後每次都是這樣計算。

代碼實現

遞歸實現

        public static int Fibonacci(int n) {
            if (n <= 1) return n;

            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }

迴圈實現

        public static int Fibonacci2(int n)
        {
            if (n <= 1) return n;

            int first = 0;
            int second = 1;
            int result = 0;
            for (int i = 2; i <= n; i++)
            {
                result = first + second;
                first = second;
                second = result;
            }

            return result;
        }

斐波那契數列求和

        public static int FibonacciSum(int n) {
            if (n <= 1) return n;
            int first = 0;
            int second = 1;
            int temp = 0;
            int result = first + second;
            for (int i = 2; i <= n; i++) {
                temp = first + second;
                first = second;
                second = temp;

                result = result + temp;
            }

            return result;
        }

斐波那契數列求和，利用公式計算

        public static int FibonacciSum2(int n)
        {
            if (n <= 1) return n;
            int first = 0;
            int second = 1;
            int temp = 0;
            for (int i = 2; i <= n; i++)
            {
                temp = first + second;
                first = second;
                second = temp;
            }

            int result = 2 * second + first - 1; //Sn = 2an + an - 1 - 1

            return result;
        }

測試

        [Fact]
        public void Test0()
        {
            Assert.Equal(0, Coding007.Fibonacci(0));
            Assert.Equal(0, Coding007.Fibonacci2(0));
            Assert.Equal(0, Coding007.FibonacciSum(0));
            Assert.Equal(0, Coding007.FibonacciSum2(0));
        }

        [Fact]
        public void Test1()
        {
            Assert.Equal(1, Coding007.Fibonacci(1));
            Assert.Equal(1, Coding007.Fibonacci2(1));
            Assert.Equal(1, Coding007.FibonacciSum(1));
            Assert.Equal(1, Coding007.FibonacciSum2(1));
        }

        [Fact]
        public void Test2()
        {
            Assert.Equal(1, Coding007.Fibonacci(2));
            Assert.Equal(1, Coding007.Fibonacci2(2));
            Assert.Equal(2, Coding007.FibonacciSum(2));
            Assert.Equal(2, Coding007.FibonacciSum2(2));
        }

        [Fact]
        public void Test3()
        {
            Assert.Equal(2, Coding007.Fibonacci(3));
            Assert.Equal(2, Coding007.Fibonacci2(3));
            Assert.Equal(4, Coding007.FibonacciSum(3));
            Assert.Equal(4, Coding007.FibonacciSum2(3));
        }

        [Fact]
        public void Test4()
        {
            Assert.Equal(3, Coding007.Fibonacci(4));
            Assert.Equal(3, Coding007.Fibonacci2(4));
            Assert.Equal(7, Coding007.FibonacciSum(4));
            Assert.Equal(7, Coding007.FibonacciSum2(4));
        }

        [Fact]
        public void Test5()
        {
            Assert.Equal(5, Coding007.Fibonacci(5));
            Assert.Equal(5, Coding007.Fibonacci2(5));
            Assert.Equal(12, Coding007.FibonacciSum(5));
            Assert.Equal(12, Coding007.FibonacciSum2(5));
        }

        [Fact]
        public void Test6()
        {
            Assert.Equal(8, Coding007.Fibonacci(6));
            Assert.Equal(8, Coding007.Fibonacci2(6));
            Assert.Equal(20, Coding007.FibonacciSum(6));
            Assert.Equal(20, Coding007.FibonacciSum2(6));
        }

想入非非：擴展思維，發揮想象

1. 熟悉遞歸
2. 熟悉斐波那契數列
3. 斐波那契數列求和
4. 知道有公式的就用公式，不要自己去迴圈就算，就像1+2+3+......，用高斯定理直接算結果，不要再迴圈了