有奖答题！！关于＂递归＂答对送分！!

Question

long fib(int n)
void main()
{
    cout<<fib(8)<<endl;
}
long fib(int n)
{
   switch(n)
   {   
      case 0: return 0;
      case 1:
      case 2: return 1;
   }
   return fib(n-1)+fib(n-2);　//他是如何返回值的？
}结果是：21;我的问题是＂21＂是如何得来的？
能给出详细递归步骤吗!!　
谢谢了！！！啊！！

Answer 1

fib(8)->fib(7)+fib(6)
其中fib(7)->fib(6)+f(5),fib(6)->fib(5),fib(4)
……最后分解到fib(2)或者fib(1)共21次

Answer 2

fib(1)=1
fib(2)=1
fib(3)=fib(2)+fib(1)=2
fib(4)=fib(3)+fib(2)=3
fib(5)=fib(4)+fib(3)=5
fib(6)=fib(5)+fib(4)=8
fib(7)=fib(6)+fib(5)=13
fib(8)=fib(7)+fib(6)=21

Answer 3

递                             归
   |   fib(8) = fib(7) + fib(6)    A  = 13 + 8 = 21 
   |   fib(7) = fib(6) + fib(5)    |  =  8 + 5 = 13
   |   fib(6) = fib(5) + fib(4)    |  =  5 + 3 =  8
   |   fib(5) = fib(4) + fib(3)    |  =  3 + 2 =  5
   |   fib(4) = fib(3) + fib(2)    |  =  2 + 1 =  3 
   |   fib(3) = fib(2) + fib(1)    |  =  1 + 1 =  2
   |   fib(2) = fib(1) + fib(0)    |  =  1 + 0 =  1
   |   fib(1) = 1
   V   fib(0) = 0