师：同学们好，在今天的算法与程序设计课上，我将带领大家学习一种有趣的算法——递归。看到屏幕上的这张图片，同学们是不是觉得有点眼花呢？其实这种现象被称之为德罗斯特效应。德罗斯特效应是指一张图片的某个部分和整张图片相同，如此产生无限循环的一种视觉形式。这种视觉形式就是我们今天所讲的递归现象。在生活中同学们遇到过这种形式吗？你们有没有走进过一个对面墙壁都安装了镜子的电梯，在镜子里你们能看到什么？或者有的同学听过这样一个故事：从前有座山，山里有个庙，庙里有个老和尚和小和尚。一天，老和尚给小和尚讲故事：从前有座山，山里有个庙，庙里有个老和尚和小和尚。一天，老和尚给小和尚讲故事……
生：……
师：不错，递归现象，简单地说就是自己包含自己。病毒与细菌威胁着我们的健康，因为这些家伙可以通过一个自己复制出许许多多的自己。我们以细菌为例，一个细菌可以分裂成两个细菌，两个细菌可以分裂成4个细菌，无穷无尽，这是不是也形成了一种递归现象？为了预防它们，最有效的方式就是洗手，如果不洗手，我们的手上会发生什么呢？下面就请同学们计算在下面这个场景当中你们手上的细菌数目。假设你们手上此刻有100个细菌，细菌的繁殖速度按每30分钟繁殖一代计算。在没有洗手的情况下，4个小时后你们手上的细菌数目是多少？
生：……
师：同学们应该很快想到了，利用循环的方式，按照一定规则从前往后进行8次计算，很快就能得到结果。其实这种方法我们称之为递推法。那么今天同学们不妨跟着老师换一个思路，用不一样的方法来解决这个问题。假设最初手上的细菌数为100，以函数的形式记为F0。我们从结论出发，将第8次细菌分裂的结果以函数的形式记为F8，那么细菌第8次分裂的结果可以由第7次细菌分裂的结果乘以2得出。但此时我们并不知道第7次细菌分裂的结果是多少，但我们知道第7次细菌分裂的结果等于第6次分裂的结果乘以2，以此类推，我们可以得到第一次细菌分裂的结果为最初手上的细菌数乘以2。
此时我们明确知道最初手上有100个细菌，我们将100返回给第一次细菌分裂的计算表达式，得到结果200。再将200返回给第二次细菌分裂的计算表达式，得到400。再将400返回给第三次细菌分裂的计算表达式，得到结果800。按照这个方法回溯到第八次，得到结果25600。在这个过程中，我们归纳出了一个细菌分裂的计算通用表达式，从未知的F8开始递推到已知的F0，再将已知数据依次返回上层，利用表达式最终计算出F8的值，这就是递归算法的思路。同学们请想一想，我们的表达式这样写完整吗？
生：不完整。
师：很显然是不完整的，因为这里没有反映出当参数为0时要结束递归返回数值。所以正确的表达式应该是这样的。也就是说在这个表达式中一定要体现递归结束条件，当参数缩小到什么程度时，结束递归返回数值。我们用程序如何实现呢？在第二章的学习中，同学们已经掌握了自定义函数的用法，递归算法的实现就是在函数的定义中调用函数自身。请看我们的代码，是不是非常简洁呢？我们的程序分为两部分，主程序部分仅有一句话，用来实现在窗体上显示结果。自定义函数部分也仅有一句话，函数体内通过分支来判断是否满足递归结束条件。分支语句的条件表达式判断函数的参数是否为0，如果满足则直接返回100，如果不满足则缩小参数规模，利用表达式实现递归调用。到此我们了解到递归算法就是一种直接或间接调用自身函数的算法。通俗地说，递归算法的实质就是将问题分解成同类问题的子问题，然后递归调用表示问题的解。通过上面的例子，我们来总结一下递归算法实现的必要条件。我们不妨也来个灵魂三问：我是谁？我从哪来？我到哪去？明确你这个函数要干什么，先不管函数里面的代码是什么，而是先要明白你这个函数的功能是什么，要完成什么样的一件事。“我从哪来”，找出函数的等价关系式，我们要不断缩小参数的范围，缩小之后我们可以通过一些辅助的变量或者操作得到原函数的结果。“我到哪去”，就是要寻找递归结束条件，我们不断缩小参数范围后，要找到一个参数的值，能够直接知道函数的结果是什么，此时递归结束，直接把结果返回。这就是递归实现的三大要素。
遇到问题时，我们不妨先问一下这3个问题，如果你能顺利回答，我们就可以用递归算法来解决啦。下面请同学们来看一下这个著名的非布尔代数兔子问题。意大利的著名数学家斐波那契提出了一个兔子问题，假定小兔子一个月可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底将有多少对兔子，当然得假设在这个过程中没有兔子死亡，并严格按照以上的规律长大和繁殖。
要想解决这个问题，我们可以用表格来分析一下每个月的兔子数。表格的3行分别表示小兔子的数量、大兔子的数量以及兔子总数。第一个月我们仅拥有一对小兔子，第二个月时小兔子则长成了大兔子，并没有新的兔子出生。第三个月的时候，之前的一对大兔子生出了一对新的小兔子，大兔子的数目仍然为一对，所以3月共拥有两对兔子。到第四个月之前，所有的两对兔子都成为了大兔子，而其中有一对大兔子可以生出一对新的小兔子，所以4月共拥有3对兔子。
到第五个月的时候，之前的三对兔子成为了大兔子，其中有两对兔子可以生出两对新的小兔子，所以第五个月的时候我们拥有5对兔子。到第六个月之前的5对兔子都成为了大兔子，其中有3对兔子可以生出3对新的小兔子，所以6月共拥有8对兔子，以此类推。在第12个月的时候，我们将拥有89对大兔子，其中55对大兔子可以生出新的小兔子。最终到年底我们就拥有了144对兔子，数目是不是很惊人呢？以上是我们的递推过程，同学们发现了其中的规律吗？以第6个月为例，我们当月拥有的兔子由大兔子和小兔子组成。6月大兔子的数量是不是等于5月兔子的总量呢？那6月的小兔子将由5月所有的大兔子生出，那数量也就等于5月大兔子的数量，这个数量其实也就是4月所有兔子的数量。所以6月拥有的兔子数就等于5月的兔子总数加上4月的兔子总数。我们将每个月的兔子数记为函数FIB，就可以得出每个月兔子数的函数FIB(n)=FIB(n - 1)+FIB(n - 2)。
那么这个递归表达式完成了吗？很显然没有，我们要找到递归结束条件。在这个例子当中，当月份是1月和2月的时候，我们明确地知道兔子的数量只有一对。所以当月份这个参数小于3时，我们可以直接得到结果。正确的递归表达式应该是这样的，递归三要素具备了，我们就可以编程实现了。同学们请看这段代码，是不是觉得太简洁了？这段程序同样由两个部分组成，主程序和自定义函数。主程序中一句话用以实现在窗体上显示结果，自定义函数中用一个分支语句实现递归调用。老师隐去了关键的表达式，请同学们思考一下，在这三个位置上应该填写怎样的表达式呢？