师：同学们，今天我们一起学习高一必修一教科版信息技术第四单元第三节中的非数值计算之递归。之前我们已经学习了用Python语言实现顺序结构、分支结构、循环结构的程序，以及Python函数的定义与调用。这节课在此基础上学习递归算法，并编写解决汉诺塔游戏的程序。我们先来看求n的阶乘的函数定义与调用。
在求n阶乘的函数中，先给s赋初值1，然后用一个for循环将2到n累乘到s，最后返回s的值，这就是n阶乘的结果。程序执行时，从主程序第一行“total = factorial(4)”开始，调用factorial函数求4的阶乘，得到结果24后返回到调用处，给total赋值为24，输出结果为24。
这里，n的阶乘等于1乘2一直乘到n，n - 1的阶乘等于1乘2一直乘到n - 1 。由此可得n的阶乘等于n乘以n - 1的阶乘。要求4的阶乘，按照递推式，4的阶乘等于4×3的阶乘，3的阶乘不知道就继续推导，3的阶乘等于3×2的阶乘，2的阶乘等于2×1的阶乘，很明显1的阶乘是1，再倒推回去就能求出4的阶乘。利用这种思想，我们可以写出与上面算法不同但功能同样是求n阶乘的程序，运行这个程序，输出结果也是24。
大家看看这个程序，它与前面的程序有哪些不同呢？整个函数体都不一样，这个程序有两个不同特点：一是有两个return语句，即根据不同条件有不同出口；二是第二个return语句后面也有一个factorial函数名，只是后面的参数比n小，变成n - 1。当调用factorial函数求4的阶乘时，给形参n赋值为4，执行函数体求4的阶乘。由于4不等于1，因此执行else后面的语句，再次调用factorial函数求3的阶乘。注意，当求出3的阶乘，其值一定是返回到调用函数的这个位置。
基于上面的分析，我们来看看程序的执行过程。程序执行时，调用factorial函数求4的阶乘，按照函数定义，4不等于1，4的阶乘等于4乘以3的阶乘，于是又调用这个函数求3的阶乘；按照函数定义，3不等于1，3的阶乘等于3乘以2的阶乘，又调用这个函数求2的阶乘；按照函数定义，2不等于1，2的阶乘等于2乘以1的阶乘，又调用这个函数求1的阶乘；按照函数定义，1的阶乘就是1，乘以2就求出了2的阶乘等于2，返回到调用求2的阶乘这个语句中，乘以3，求出3的阶乘为6，返回到调用3的阶乘这个语句中，乘以4就求出了4的阶乘为24，返回时就求出了4的阶乘。
从刚才的分析可以看出，这个函数的调用执行过程分为两个阶段，一个是递推调用阶段，另一个是逐层回归阶段。大家理解这个函数的执行过程了吗？这个函数当n大于1时，很明显是自己调用自己，只不过参数变小。像这样直接或间接地调用自身的方法称为递归。递归是计算科学领域中一种重要的计算思维模式，它既是一种抽象的表达手段，也是一种问题求解的重要方法。
求n阶乘的递规定义为：当n等于1时，n的阶乘是1，这是边界条件；当n大于1时，n的阶乘等于n乘以n - 1的阶乘，这是递推关系式。从上面递归的定义可以得出，递推关系是递归的重要组成部分，而边界条件是递归的另一个要素，它保证递归能在有限次的计算后得出结果，而不会产生无限循环。递归的基本思想是将规模较大的问题层层转化为规模较小的同类问题。
从上面的分析，我们能体会到编写递归程序重点在于编写递归函数，一般有三步：第一步，明确函数的功能，确定接受什么参数，有没有返回值，若有则返回值代表什么意思；第二步，确定递归结束的边界条件，当参数为何值时，不再调用函数，递归结束，也就是必须有一个明确的结束条件，满足这个条件就不用递推下去，而是开始逐层回归；第三步，确定递推关系式，有些递归函数是Fn与Fn - 1、Fn - 2等之间的关系式，因为递归是把规模较大的问题转换为规模较小的同类问题求解。
下面我们就用编写递归的思想解决实际问题，编写有关汉诺塔程序。如图所示，木板上有a、b、c三根杆，a杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从a杆全部移到c杆上。要求：一、求出最小移动次数；二、输出将木盘从a杆移动到c杆的每一步移动过程。
先来看确定求最小移动次数汉诺塔递归函数的过程：第一步，明确函数的功能，确定接受什么参数，这里参数是木盘的个数n，返回值是n个木盘的最小移动次数；第二步，确定递推结束的边界条件，只有一个木盘时，最小移动次数为1；第三步，确定递推关系式，一般来说，递推关系式比较难一下子找出来，要经过推导，比如求n阶乘的递推关系式，或者先用一些特殊的值去尝试得出结论，然后再推广到一般情形。在汉诺塔游戏中，可以先用比较少木盘的情况去感受一下得出结论，再推广到一般情形。