///一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少， 用递归算法实现。
public static long foo(int i)
{
if (i <= 0)
return 0;
else if (i > 0 && i <= 2)
return 1;
else return foo(i - 1) + foo(i - 2);
}
从规则不难看出位数与数字的关系是：从第3个数开始，每个数是前两个数的和.
if (i <= 0) return 0 //预防输入0或负数，输入则返回“0”；
else if (i > 0 && i <= 2) return 1; //如果输入第1位或第2位，则返回“1”（如题）
else return Foo(i - 1) + Foo(i - 2);”输入其它的数则返回前两个数的值。注意：因为求数列中每一个值都是调用该函数，所以求前两个数的值就又要调用2个这个函数。这就是递归（调用自身）。
假设 算第三位的数 那么foo(3-1)+foo(3-2) = foo(2)+foo(1) = 1+1= 2;
求Foo（30）的值，则返回Foo(29) + Foo(28)的值，其中又要调用Foo(29) 和Foo(28)求它们的值，Foo(29)又要调用Foo(28)和Foo(27)，Foo(28)又要调用Foo(27)和Foo(26)……直到调用Foo(2)和Foo(1)会返回“1”，又一层层代回去，最后加出正确答案