哪位大哥能帮我分析下啊？这个递归算法，我不知道为什么
class Class1
{
/// <summary>
/// 应用程序的主入口点。
/// </summary>
[STAThread]
static void Main(string[] args)
{
//
// TODO: 在此处添加代码以启动应用程序

Console.WriteLine(Foo(4).ToString());
}
//
static int a;
public static int Foo(int i)
{
if (i <= 0)
return 0;
else if(i > 0 && i <= 2)
return 1;

else a=Foo(i -1) + Foo(i - 1);
return a;
}
}


[解决办法]
Foo(2) = 1;
Foo(3) = Foo(2) + Foo(2) = 1 + 1 = 2;
Foo(4) = Foo(3) + Foo(3) = 2 + 2 = 4;

[解决办法]
1,2,4,8,16
1,1+1,2+2,4+4,8+8