递归和循环:斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数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+......，用高斯定理直接算结果，不要再循环了