求解斐波那契数列--小白篇
一级目录 递归法
********递归法就是函数自身调用自己的技巧************ **********递归的两个必要条件:********
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; }
三级目录 如何理解递归呢?
可以试着从函数栈帧方面思考:
每一次函数调用都会为本次函数调用分配空间(是在内存的栈区上的)
为本次函数调用分配空间的叫做这个函数调用的栈帧区间。
内存被分为栈区和堆区还有静态区。
申请空间是自下而上的申请到的,而调用完后的函数所分配的空间还给内存时是自上而下销毁的 ,这与递归的思想相似。
以上是我个人的观点,我是小白 勿喷哇!!!谢谢!!!