浅谈递归算法

先看一下一般的做法
//{1,1,2,3,5,8,^}求第三十个数的值（一般做法）
        protected static int fun2(int n)
        {
            int sum = 0;
            int b = 1;
            int a = 1;
            if (n==1)
        {
        return a;

        }
            else if (n==2)
        {
        return b;
        }
            else if (n>=3)
        {
        for (int i = 0; i < n - 2; i++)
                {
                    sum = a + b;
                    a = b;
                    b = sum;
                }
                return sum;
        }
            else
            {
                //Console.WriteLine("你输入的数据有误");
               throw new Exception("你输入的数据有误");
            }
这种做法程序不太理智，效率不高。我建议各位面试时要是考到这方面知识，千万别弄几个for循环给人家，除非非不得已，（我有朋友，人家考官一看，当场就game over）

推荐用以下，我知道比较好的算法
        //{1,1,2,3,5,8,^}求第三十个数的值(递归算法)
        protected static int fun1(int n)
        {
            if (n == 1)
            {
                return 1;
            }
            if (n == 2)
            {
                return 1;
            }
            else
            {
                return fun1(n - 1) + fun1(n - 2);
            }
            //return n;
        }

        //累加的递归
        public static int fun(int n)
        {
            return n <= 1 ? 1 : (n + fun(n - 1));
        }