例7－11 设计一个计算n!的递归程序。
根据数学含义，n!可由下面的公式表示:
根据以上公式推理，为了求n!，可以先求出(n－1)!，为了求(n－1)!又可先求(n－2)!……以此类推，直到n＝0。由于n＝0时n!已定义为1。再由0!＝1一步步反向推回，求出1!、2!……最终得到n!的值。下面将此过程写成递归函数。
程序代码如下:
在运行时，输入3，输出结果为:
下面看输入3后程序是如何执行的。
(1)当主程序的cin>>n读入3后，执行x＝fct(3)引起第一次调用fct(3)，进入fct函数体，由于n＝3大于0，所以执行语句return 3∗fct(3－1)，即return 3∗fct(2)。
(2)为了求得fct(2)，又引起第二次的函数调用(递归调用)。重新进入fct函数体，此时值参n＝2仍然大于0，执行语句return 2∗fct(2－1)，即return 2∗fct(1)。
(3)为求得fct(1)又引起第三次函数调用(递归调用)，进入函数体，这时值参n＝1大于0，执行语句return 1∗fct(1－1)，即return 1∗fct(0)。
(4)为求得fct(0)又第四次调用函数(递归调用)，进入函数体，这时值参满足n＝0的条件，故执行if后面的语句return 1。
(5)当第四次调用求得fct(0)＝1时就不再产生递归调用，程序返回到第三次的调用点，执行return 1∗fct(0)。由于fct(0)＝1，结果为fct(1)＝1∗1＝1，完成第三次调用。继续返回第二次的调用点，求得fct(2)＝2∗1＝2，完成第二次调用，同理继续返回第一次调用点，算出fct(3)＝3∗2＝6。第一次调用结束后，返回主程序的赋值语句x＝fct(n)，输出结果3!＝6。
为了便于理解以上程序的执行过程，请参考如图7－2所示的递归调用的示意图。
图7－2 递归调用示意图
例7－12 编程解决汉诺塔问题。相传古印度所罗门教徒玩一种游戏，将64片直径不同中心有孔的圆形金片穿在一根金刚石柱子上，小片在上，大片在下，形成宝塔形状(如图7－3所示)。按照下述三条规则，把这些金片从原来的柱子(杆A)一片片地搬到另一个柱子(杆B)上，当完成整个游戏即放下最后一片金片时，会听到“轰”的一声天崩地裂，宇宙就毁灭了。三条规则是:
图7－3 汉诺宝塔
(1)只给一根中间过渡杆(杆C)。
(2)每次只能从一杆顶端取下一个金片，放在另一杆上。
(3)任何时候，任一杆上的金片，都要满足小的在上面、大的在下面(即大片不能压小片)。
分析:这是一个非常好的递归程序设计示例。它不像前面的递归程序那样，先有非递归程序，再将其改写成递归形式。如果此题不使用递归过程或许你无从下手。下面先以三个金片为例。
要从杆A移动到杆B，要借助于杆C来过渡。移动方案是:
第一步A→B(表示将杆A的金片移动到杆B上)；
第二步A→C；
第三步B→C；
第四步A→B；
第五步C→A；
第六步C→B；(www.xing528.com)
第七步A→B。
共移动7次，完成了将A杆上的三个金片按照题目要求的规则移到了B杆上。
题目要求将n个金片由杆A移到杆B，可用同样的方法:
(1)(递归地)将杆A上面的n－1片移到杆C(利用杆B)。
(2)把杆A上唯一的一片移到杆B。
(3)再把杆C上的n－1片(递归地)移到杆B(利用杆A)。
这是一个递归调用过程。程序代码如下:
运行结果如下:
当程序运行输入n的值时，除3以外也可以选4、5或6，但千万不要输入64。因为通过推导，若按规则移动64片金片，要搬动264－1＝1.8×1019次。若每秒钟移动一次，需一万亿年。根据科学推算，地球的“生命”几十亿年到几百亿年，可见到地球毁灭也不能做完这个游戏。即使让计算机“搬”，每秒搬一亿次，也要用5 800年，可见要完成这个游戏是不可能的。
由以上两个递归函数的执行过程可以看到，每次递归调用，总是重复执行某种操作，这与循环有点近似。
递归结构的程序具有结构清晰、容易阅读和理解的优点，写出的程序较简短，但在处理递归问题中，需要保留每次递归调用时的参数和局部变量，这样就占用大量的存储空间和花费较多的机器时间，效率较低。
用递归过程或函数解决问题时应满足下面的要求:
(1)分析题意，求解的问题是否符合递归的描述:将要解决的问题化为与原问题相同的若干子问题。
(2)函数体中必须有递归结束的条件，即不进行递归的条件判断语句。
(3)递归调用的次数是有限的。不管递归调用多少次，每递归一次，即向递归结束条件接近一点，最终达到结束条件，不再递归。
一、指出下面程序中哪些是形式参数，哪些是实际参数
二、指出下面程序中哪些是全局变量，哪些是局部变量
三、写出下面程序的输出结果
四、编程题
1.编写函数，函数功能是:统计整数n的各位上出现数字1、2、3的次数。要求输入/输出均在主函数中完成。
2.编写两个函数，函数功能是:求出两个整数的最大公约数和最小公倍数，要求输入/输出均在主函数中完成。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
