斐波那契数列

定义：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            int ret1 = FibonacciSort(10);
            int ret2 = FibonacciSort2(10);
            Console.WriteLine("斐波那契数列，递归算法：{0}",ret1);
            Console.WriteLine("斐波那契数列，普通算法：{0}", ret2);
        }

        /// <summary>
        /// 斐波那契数列，递归算法
        /// </summary>
        /// <param name="num"></param>
        public static int FibonacciSort(int num)
        {
            if (num <= 0)
            {
                return 0;
            }else if (num > 0 && num < 3)
            {
                return 1;
            }else
            {
                return FibonacciSort(num - 1) + FibonacciSort(num - 2);
            }
        }

        /// <summary>
        /// 斐波那契数列，普通算法
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public static int FibonacciSort2(int num)
        {
           if (num <= 0)
            {
                return 0;
            }
            else if (num > 0 && num < 3)
            {
                return 1;
            }
            int ret = 0;
            int num1 = 1;
            int num2 = 1;
            for (int i = 0; i < num - 2; i++)
            {
                ret = num1 + num2;
                num1 = num2;
                num2 = ret;
            }

            return ret;
        }
    }
}

运行结果： image.png