请asp.net高手来帮我看一下这个程序的算法

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); 
} 
} 
感觉这程序老是绕不出来，在return Foo（i-1）时就调用Foo（int i）方法还是在Foo（i-2）时调用。。return Foo(i -1) + Foo(i - 2);它们有什么联系啊。还有这道题是在什么时候返回第30项的值的。
请高手指点迷津谢了

Answer 1

你都没有循环，
改了一下，好像还是繁琐了一点，参考一下： public static int Foo(int i)
    {
        if (i <= 0)
            return 0;
        else if (i > 0 && i <= 2)
            return 1;
        else
        {
            int[] sum = new int[i];
            sum[0]=1;
            sum[1]=1;
            for (int j = 2; j < i; j++)
            {
                sum[j] = sum[j - 1] + sum[j - 2];             }
            return sum[i - 1];
        }
    }

Answer 2

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 3

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 4

public static int Foo(int i)
        {
            if (i < 3)
            {
                return 1;
            }
            else
            {
                return Foo(i - 1) + Foo(i - 2);
            }
        }        static void Main(string[] args)
        {
            Console.WriteLine(Foo(30));
        }