递归算法,求救！

Question

class Program 
    { 
        public static int Foo(int i) 
        { 
            Console.WriteLine(i); 
            if (i <= 0) 
                return 0; 
            else if (i > 0 & i <= 2) 
                return 1; 
            else 
                return Foo(i - 1) + Foo(i - 2); 
        } 
        static void Main(string[] args) 
        { 
            Console.WriteLine(Foo(6)); 
        } 
    } 输出结果是： 
6 
5 
4 
3 
2 
1 
2 
3 
2 
1 
4 
3 
2 
1 
2 
8 
请按任意键继续. . . 为什么最后是8 ? 能否一步一步的写给我看看编译器怎么运算到最后的？帮帮忙，谢谢。

Answer 1

x=0时 y=0
x=1   y=1
x=2   y=1
x=3   y=1+1=2
x=4   y=1+2=3
x=5   y=2+3=5
x=6   y=3+5=8

Answer 2

1+1=2 
1+2=3
是从那里来的?和Foo(i-1)+(Foo-2) 有什么联系?

Answer 3

6
5
4
3
2
1
x=1;y=1
2
x=2;y=1
3
2
1
x=1;y=1
x=3;y=2
4
3
2
1
x=1;y=1
2
x=2;y=1
x=5;y=3
8

Answer 4

foo(6) = foo(5) + foo(4) = 2foo(4) + foo(3) = 3foo(3) + 2foo(2) = 5foo(2) + 3foo(1)foo(2)  = 1
foo(1)  = 1foo(6) = 5 + 3 = 8

Answer 5

shrinerain(圣影雨) ( ) 信誉：100 
 的算法
x=0时 y=0
x=1   y=1
x=2   y=1
x=3   y=1+1=2
x=4   y=1+2=3
x=5   y=2+3=5
x=6   y=3+5=8输入Foo(x) = y