一个算法题

Question

一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少， 用递归算法实现。
答：public class MainClass 
                  { 
                  public static void Main() 
                  { 
                  Console.WriteLine(Foo(30)); 
                  } 
                  public static int Foo(int i) 
                  { 
                  if (i <= 0) 
                  return 0; 
                  else if(i > 0 && i <= 2) 
                  return 1; 
                  else return Foo(i -1) + Foo(i - 2); 
                  } 
                  } 不是很明白
有没有更简洁的写法

Answer 1

杨辉三角吧，你首先得知道上面的数列是什么规律，然后就好写算法了
上面的规律是从第3个开始，每个数都等于前两个数之和，所以递归时，i<=2时返回1，其他都是等于前两个数之和，即Foo(i-1)+Foo(i-2)

Answer 2

列个类似递归的写法
 Func<int, int> fib = null;            
            fib= n => (n <= 2) ? 1 : fib(n - 1) + fib(n - 2);
            Console.WriteLine(fib(30));

Answer 3

也可以非递归求斐波那契数列,效率比递归高
   
                   public static void Main() 
                   { 
                   Console.WriteLine(fib(30)); 
                   } 
        public static int fib(int n)
        {
            if (n < 3)
                return 1;
            else
            {
                int a = 1;
                int b = 1;
                for (int i = 2; i < n - 1; i++)
                {
                    b = a + b;
                    a = b - a;
                }
                return a + b;
            }
        }