龚老师的电脑最近脾气很大，因为最近我总让它做枚举算法，可把它累坏了。枚举算法大家还记得吧，先来复习一下找找为什么电脑脾气这么大！枚举算法设计模式：1.分析题目，确定可解的范围。2.设计循环结构，包括循环次数和判断条件，在循环体内对可能解逐一判定，直至求出问题解。3.为了提高解决问题的效率，使可能解的范围降至最小。注意，小心电脑罢工！

注意小心电脑罢工！看来我的电脑最近在琢磨着罢工了，得学习个新的算法来缓解下电脑压力了！枚举算法是个值得我们每个人都学习的持之以恒的好同学，但有时候显的不够聪明，今天我们来认识“聪明”点的算法——递推算法。

递推算法青出于蓝而胜于蓝，继承了枚举算法持之以恒的精神，又取巧的先来找一找规律。递推算法以“起点”为基础，运用相同的运算规则，逐次重复运算，直至得出结论、运算结束。聪明的你想一想，如果以“终点”为基础，依照运算规则重复运算，算不算递推算法呢？递推算法分两种模式，一：顺推。从已知条件开始，逐步推算出问题的解。二：逆推。现在知道刚才的答案了吧？算，递推算法，还时逆推算法。

递推算法设计模式：1.分析题目已知条件和结果之间的联系【例如，1,1,2,3,5,8  找出联系了吗？】。2.设计循环结构，包括循环次数和判断条件，在循环体内对可能解逐一判定，直至求出问题解。

头昏脑涨的同学估计要说：好了说得那么厉害，那这玩意到底干啥的？递推算法在数学各个领域中都被广泛的运用着，我们来看个实例吧。【今天来点简单的开胃菜！】

小试牛刀：

满足F1=F2=1,Fn=Fn-1+Fn-2的数列我们叫做斐波那契数列，（Fibonacci）它的前若干项是：1，1，2，3，5，8，13，21，34…求此数列的第n项。

小提示：题目意图是让我们输入一个数，让电脑帮我们在斐波那契数列中找到那个位置上的数字。【例如我输入4，电脑会把斐波那契数列中第四个数字3输出来。】既然要在斐波那契数列中找数字，第一步得研究出这个数列有什么规律吧？斐波那契数列？听起来就像某个数学大师来折腾我们的的杰作。据说递推算法这功夫在数学世界中游奇效？

1.解法分析：

递推算法设计模式：1.分析题目已知条件和结果之间的联系。已知条件：【1，1，2，3，5，8，13，21，34…】，规律显而易见，从第三个数字开始，前两个数字之和等于第三个数字【例如：3+5=8,5+8=13,8+13=21】。我们先把数字列出来，第一个数字：f1，第二个数字：f2，第三个数字：f3。f3=f1+f2【f1+f2的值，赋值给f3。】第一个加法式子搞定了，再来研究第二个式子，姑且把第四个数字叫为：f4，f4=f2+f3。看起来也对，可是之后的第五个数字，第六个数字都需要f5，f6....吗？明显是不合理的，电脑可不希望你这么无知的分配空间。

那么回看看，刚刚f3=f1+f2之后，f1还有用吗？第四个数字是第三和第二数相加，其实至始至终都只用了3个数字，那么我们拿3个变量来存放这3个数字就ok了，何必要F5，F6呢？

2.代码实现

聪明的你搞定了没？

3.代码详解：

运用递推算法首先要研究出一串数字间的规律，我们确定规律发现只需要3个变量来存放不断变换的数字，那么首先来3个变量，f1, f2, f3。按题目要求，我们手动输入n的值，告诉电脑我们需要输出第n个位置上的数。既然第n个位置，那么循环找起来吧，从第一个位置找还是从第三个位置找？

第一，第二数为1，从第三数开始符合规律，当然是从第3个位置开始，至少三个数才符合我们发现的规律：f3=f1+f2，既然f1, f2已经用完了，首先把f2的值存放到f1之内，反正f1的数字已经没用了【好好理解这部分！】。接着把f3的值放到f2之内，反正f2的值已经放到了f1内。【好好理解这部分！】。

按照我们安排的规律，循环我们要找到的第n个位置，那么乖乖输出正确答案吧。

4.代码升级：

别高兴太早，严谨的态度才能让你显得更靠谱哦！让程序输出第一个位置，第二个位置看看？EXM？电脑似乎疯了？找一找哪里有问题呢？

通过某个已观察出的条件，利用特定规律得出中间推论，然后逐步递推直至得出结论。递推算法可是在数学世界中有着举足轻重的地位，你学会了吗？