Fibonacci 本以为毕业了就永别的斐波那契v^v

递归解决斐波那契

…那什么是递归呢？

高情商：阿涛给兄弟们找了相对权威的解释，兄弟们自行理解！！
低情商：我这里躲个懒，其实我自己也讲不太清楚，你们自己看着办吧！！！
其实递归啊，就是把一个大的问题分解成许多一样的小问题，打的就是精锐，玩的就是以小博大！
这里先给大家浅浅地讲解一波吧！
n！大家应该都学过吧，我给大家伙敲一个求n阶乘的代码哈！

int n = 0;
	int ret = 1;
	scanf("%d",&n);
	while (n)
	{
		ret *= n;
		n--;
	}

运用这个程序就可以自由计算一个数的阶乘了，但就像我刚才说的递归的思想是把大化小，这个思想似乎并没有在这里得到很好的体现，emmm，我们先这样思考，n!=n*(n-1)!=n*(n-1)*(n-1)!..这样子，我们一直写下去是不是一定可以直接写出从n乘到1，酱紫不就是完成了n的阶乘这个操作了吗 ？但是我们上面的这个是靠着循环实现的啊，我知道你很急，但是你现在先别急！
阿涛先教着大家如何思考，如何用递归的思维去思考！我们假设写一个函数来实现递归，如下：

int jiecheng(n)
{


}
int main()
{
	int n = 0;
	scanf("%d",&n);
	int m = jiecheng(n);
	printf("%d",m);
	return 0;

那么如果jiecheng(n)代表着n！，那么jiecheng（n-1）是不是就代表着（n-1）！同时我们的jiehcneg（n）是不是就等于n*jiecheng（n-1）》但是呢，我们这里只写了一个函数，至少在现在还没有办法在保留数据的前提下不用循环语句实现数据的叠加，那怎么呢？

相信兄弟们每每打完一个程序，都会在末尾来上这么一行，阿涛几个月前学习的时候还问过我的老师，这个return 0是什么意思，为什么总是返回它不返回别的东西，当时我的老师告诉我的是因为这里我们开头就用了main函数，只要我记住在main函数的最后都要返回0，表示正常返回，至于其他的函数就需要结合具体情况，看看是返回指针，还是整型，还是void之类的。
那同样的，我们是不是可以接着返回这个函数呢？

int jiecheng(n)
{
	return n * jiecheng(n - 1);

}

相信看到这里我们有的兄弟已经乐开了花，觉得只要掌握这么多就学了一门递归了，小伙子，你还是太年轻啊！！
这里阿涛直接帮兄弟们试验一下，这边显示栈溢出，阿涛宁可丢了面子明确告诉大家，阿涛自己其实对于栈啊堆啊这些比较深层次的东西还不是很理解，就算我再好为人师也实在没有脸皮不懂装懂，但是我可以把大概意思给大家解释一下，我们在程序中每创建一个变量，每调用一个函数，都是要在内存中申请空间的，那么我们的电脑配置就算再好，就算是王校长花了几百个w装的那台机子，内存也是有限的，到了一定程度也没有内存给你挥霍了，这种时候程序就会给你报错，告诉你，小伙子，你这边栈溢出了，我空间已经是一滴都不剩了！！
同样的道理，你陷在一段过去式中许久许久，不断重温，不断反复，不断回忆，不断想象，哪怕是程序都至少还会给你报个错，那你呢？有人会来终止你的死递归吗？没有的，到最后的结局就是你把自己的cpu给烧了，也许你会说，你做的这一切都是心甘情愿，但是请你相信我，请你一定要相信我，你这样子做只会是感动自己，你的朋友也许会怀着鄙夷不解来装模做样试着理解你开导你，你的父母也许会可怜你心疼你，你到头来也只是感动了自己吧！
话说多了，我们回来继续讲！！
那么我们这个递归到底什么时候才是个头呢？到底什么时候我们结束了这个递归呢？很明显啊，当我们乘到1的时候，难道我们还要继续乘下去吗？

那么这个应该就是我能想到的比较简单的递归的例子了！
如果兄弟们耐着性子把我之前的讲解看完了，那么我们就有了一个很好的基础来学习斐波那契！
1 1 2 3 5 8 …
我们要求的是第n个斐波那契数，第一和第二个数字都是一，第三是第二加第一，第四是第三加第二…第n个就是第n-1加第n-2个，运用这个思维，我们来看接下来的代码应该就比较容易了！
当你以为你解决了所有问题的时候，新的问题也会随之而来，就比如下面的代码！

这里程序崩溃了，原因很简单，在计算这个fib数的时候我们同时进行了大量重复的运算，一根弦绷紧到一定程度不可避免的就会断，这真是个悲伤的故事，那我们有没有办法解决这个问题呢？有的，这就是我要给兄弟们讲的关于斐波那契数的第二点，非递归版本的fib！

非递归请战，我也可以！！！

按照刚才的思路，后面一个数等于前面两个数相加，那我们可不可以不进行那么多重复的计算，是我们的程序变得高效起来？其实是可以的，我们就创建三个变量，就写一个循环，每次计算结束后，我们都把后面的数赋值给前面的一个数。照着这个思维，我们不妨先来试一试！

int main()
{
	int f = 1;
	int s = 1;
	int t = 0;
	
	while (1)
	{
		int n = 0;
		scanf("%d", &n);
		int N = n;
		while (n)
		{
			if (n > 2)
			{
				t = f + s;
				f = s;
				s = t;
			}
			n--;
		}
		printf("第%d个fib数为%d",N, t);

	}
	return 0;
}

看看我们这个函数是不是写的非常之漂亮，通过赋值就完成了递归之中进行的大量重复，那么结果究竟如何呢？不出意外的话，还是会出意外的！！

不对啊，怎么前面两个数就错了呢？就因为我们这个t初始值就为零，当n小于2时，可不就是零吗？那我们再完善一波自己的代码！

int main()
{
	
	while (1)
	{
		int f = 1;
		int s = 1;
		int t = 0;
		int n = 0;
		scanf("%d", &n);
		int N = n;
		while (n)
		{
			if (n > 2)
			{
				t = f + s;
				f = s;
				s = t;
			}
			n--;
		}
		printf("第%d个fib数为%d",N, t);

	}
	return 0;
}

细心的兄弟们应该发现了，我这段代码和上一段代码有些许不同，至于为什么不同嘛，那当然是在运行的时候发现了问题并且做出了及时的修改啊！
至于为什么出问题，就留给大家自己去运行，去探索，去发现了！！！！！
希望我的这篇博客能够帮助到大家，谢谢您的观看！不妨支持一波我们小博主！！！
百年大道，你我共勉！！！！！