仔细研究以上代码案例，大致我们可以理解为，迭代是一个正向的过程，而递归是一个倒推问题。
其实关于兔子数列（斐波那契数列）这里有一个语法小坑，和大家分享一下。
它是一个1，1，2，3，5，8，13……这样的数列。我们不去纠结兔子到底怎么生的问题（一对兔子每月生一对兔子，但是要俩月后生），单纯来看数列。
f1,f2=f2,f1+f2
这一句，能否换成
f1=f2
f2=f1+f2
呢？
看似可以，实则不能。因为经过验证发现：
f1,f2=f2,f1+f2这种赋值写法，是两组变量同时赋值的。而一旦分开写，f2就成两倍f2了，因为第一句赋值先生效了。所以分开写只能用老三句：
t=f1
f1=f2
f2=t+f2
加一个临时变量。
这里的循环我们来看一下，里面的i在循环体中根本没有用到。它只是用来控制迭代次数的，保证最后的f2是我们要求的月份。这种写法我们可以学习一下，不然脑子里只有递归。
递归的写法就不纠结了，大致就是函数调用函数本身，如果是数值计算类，就是一直追溯到有值可用。下面讨论递推关系：
五种典型的递推关系
1.
Fibonacci数列
在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。
Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。
【问题的提出】
有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？
【解析】
设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对。则：
Fx=Nx+ Fx-1
Nx=Fx-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力）
所以 Fx=Fx-1+Fx-2 边界条件：F0=0，F1=1
由上面的递推关系可依次得到：
F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……。
Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，Fibonacci数列的用处也得到了较好的体现。
2.
Hanoi塔问题
【问题】
Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图3-11所示。要求把a柱上n个圆盘按下述规则移到c柱上：
1)一次只能移一个圆盘；
(2)圆盘只能在三个柱上存放；
(3)在移动过程中，不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？
【解析】
设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。
所以hn=2hn-1+1 边界条件：h1=1
3.
平面分割问题
【问题的提出】
设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
【解析】
设an为n条封闭曲线把平面分割成的区域个数。由图3-13可以看出：a2-a1=2；a3-a2=4；a4-a3=6。
1)一次只能移一个圆盘；
(2)圆盘只能在三个柱上存放；
(3)在移动过程中，不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？
【解析】
设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。
所以hn=2hn-1+1 边界条件：h1=1
4.Catalan数
Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。
问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表示，hn即为Catalan数。例如五边形有如下五种拆分方案(图3-14)，故h5=5。求对于一个任意的凸n边形相应的hn。
5.第二类Stirling数
在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。
【定义】
n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。
下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。
【解析】
设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：
①bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)；
②bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。
综合以上两种情况，可以得出第二类Stirling数定理：
【定理】
S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n>1,m1)
边界条件可以由定义2推导出：
S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。
第二类Stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。
