求解斐波那契数列--小白篇

一级目录 递归法

     ********递归法就是函数自身调用自己的技巧************
     **********递归的两个必要条件：********

1. 存在限制条件，当满足这个限制条件的时候，递归便不再继续。

2. 每次递归调用之后越来越接近这个限制条件。

斐波那契数列的特点就是从第二项开始每一项都等于前两项之和。那么从数学角度思考可以写成它的一个表达式为Fib(n)=Fib(n-1)+Fib(n-2) 当n>2时。如果n<2即为1.

代码如下：`

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

但这个代码运行效率十分低下，为什么呢，，是因为不断进行了大量重复的计算，

计算量非常大。那怎么解决呢？

二级目录 非递归法（即循环）

递归的方法计算量非常大，所以我们不使用递归的方法，用循环的方法，递归呢是从后往前想的，而正常的思考应该是从一开始往后想，只要把前两项相加就可以得到想要的数了。

![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/9a04ed68802345c1b1c5cefd28246054.png

先创建变量 a=1，b=1，c=1，把a看成第一项b看成第二项，而c 看成第三项，令c=a+b，这就得到了第第三项，可我们需要后面的项怎么弄呢，这时只要令 b的值赋给a ，c的值赋给b使这个过程进行循环就可以得到后面的项了，不过这个循环次数受n控制，当n=3 时 ， 1+1=2 2+1 =3 这时进行了两次加法计算，而当n=5时，1+1=2， 2+1=3， 3+2=5，进行了三次加法计算，所每次循环n都要减1（循环条件是n>2）代码如下：*

在这里插入代码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;
}

三级目录 如何理解递归呢？

可以试着从函数栈帧方面思考：

每一次函数调用都会为本次函数调用分配空间（是在内存的栈区上的）

为本次函数调用分配空间的叫做这个函数调用的栈帧区间。

内存被分为栈区和堆区还有静态区。

申请空间是自下而上的申请到的，而调用完后的函数所分配的空间还给内存时是自上而下销毁的 ，这与递归的思想相似。

以上是我个人的观点，我是小白 勿喷哇！！！谢谢！！！