求第n个斐波那契数。（用递归和循环的方法对比）

写这个代码的过程中出现的问题及改进方法：

1. 用递归实现

#include <stdio.h>

int Fib(int n)
{
    if (n <= 2)
        return 1;
   else
        return Fib(n - 1) + Fib(n - 2);
}
int main()
{
   int n = 0;
   int ret = 0;
   scanf("%d", &n);
   ret = Fib(n);
   printf("ret=%d\n", ret);
   return 0;
}

写好代码运行发现的问题：不考虑结果溢出的情况下，当所求n较大时，代码运行次数太多，导致n以前的数重复的计算了很多次。我试了一下当n=50时，运行大约要十来分钟才能出结果。现在计算一下当计算第n个斐波那契数时，n之前的数执行次数。

用以下代码计算小于n的一个数的执行次数：

       用以上代码计算第n个斐波那契数时，通过递归函数代码运算得到3的次数如下图，为count=39088169次（运行时也等了一会儿），就一个3就重复了这么多次，还有小于n的其它数，所以用递归求第n个斐波那契数效率很低。由此可以看出，这题使用递归的方法对于计算机执行程序来说比较繁琐，求一个数重复运行多次，当n较大时问题会明显看出问题。

2.用循环实现（可以使以上问题得到改善）

#include <stdio.h>

int Fib(int n)
{
   int a = 1;
   int b = 1;
   int c = 1;
   while (n > 2)
   {
      c = a + b;
      a = b;
      b = c;
      n--;
   }
   return c;
}

int main()
{
   int n = 0;
   int ret = 0;
   scanf("%d", &n);
   ret = Fib(n);
   printf("ret=%d\n", ret);
   return 0;
}

由以上可以看出，用递归求此题的代码运算效率低，当n较大时问题比较明显；换成用循环求解可以使该问题得到解决。