递归程序设计

1、4.6递归程序设计11.递归函数一个函数被调用，在尚未执行完之前，又直接或间接地调用了这个函数本身，这样的函数称递归函数。递归函数分为直接递归函数和间接递归函数。这种函数的示意图如下：231)直接递归函数如果一个函数在其定义中直接调用自己，则称这种函数为直接递归函数。4比如下面函数求n的阶乘，采用的是直接递归调用形式，因此是直接递归函数： long factorial(int n) if(n=0) return 1; return factorial(n-1)*n; 52）间接递归函数如果一个函数通过在其定义中调用其它函数，再由其它函数调用该函数，称这种函数为间接递归函数。6比如下面的代码定义

2、了两个函数，它们构成了间接递归调用：int f1(int a) int b; b=f2(a+1); /间接递归调用 ：f1()调用了f2() /.int f2(int a) int c; c=f1(s-1); /间接递归调用 ：f2()又调用了f1() /.在上面代码中，f1()调用了f2()，而f2()又调用了f1()，这样f1()、f2()各自实现了间接递归调用自己。72.简单递归函数举例 已知Fibonacci序列的数学定义如下： 使用递归程序计算Fibonacci数序列。8分析如下： 设n为5，则有： F(5)=F(3)+F(4) =F(1)+F(2)+F(2)+F(3) =F(1)+

3、F(0)+F(1)+F(0)+F(1)+F(1)+F(2) =F(1)+F(0)+F(1)+F(0)+F(1)+F(1)+F(0)+F(1) =1+1+1+1+1+1+1+1 =89因此可以归纳为函数：int fibonacci(int n) /n是大于等于0 的整数 if(n=0)|(n=1) return 1; if(n1) return (fibonacci(n-2)+fibonacci(n-1); 103.递归函数的特点1)至少存在一个基本解(不再递归)。2)每一次求解过程都可归结为把对一个较大较为复杂的问题的求解转化为对较为小较为简单的同类问题的求解。3)经过执行有限步之后，总能达到

4、基本解。11从求Fibonacci序列的例子分析递归函数的三大特点：121)n=0和n=1时是基本解，此时函数不用再递归，可以直接得出结果，即f(0)=1,f(1)=1。2)当n1时，f(n)总是可以通过转化为求f(n-1)和f(n-2)来实现,即f(n)=f(n-1)+f(n-2)。求f(n-1)、f(n-2)是和求f(n)同类的但较小较简单的问题。133)不论n多大，总能转化为求f(n-1)和f(n-2)来实现，而f(n-1)和f(n-2)又各自可以转化为较小较简单的问题，这样经过有限步后，总可以达到基本解，即转化为求f(0)和f(1)来实现。当然n可以无限大只是理论上的，实际上n的大小还

5、得受计算机可表示的范围限制，即n及其结果f(n)必须在int类型能表达的范围之内。把类型int改成long可以相应增大n的范围。144.汉诺塔问题1)问题描述：传说在19世纪末，Bramah神庙的教士玩一种称为梵塔(Tower of Hanoi)的游戏：共有三个柱子以及有n(n0)个能套进柱子的大小不一的盘子，盘按从小到大的顺序标号为1到n.开始时n个盘子均套在A柱上，且小的放在大的上面(如下图所示)。游戏要求按下列规则将所有的盘从A柱移到C柱，在移动过程中可以借助另一个B柱。规则1:每次只能移动柱最上面的一个盘子；规则2：任何时候都不可以把大的盘子放到小的盘子上。152)先从简单问题着手：当

6、n等于1时；移动1次(21-1次)当n等于2时;移动3次(22-1次) A-B A-C B-C当n等于3时；移动7次(23-1次) A-C A-B C-B A-C B-A B-C A-C当n为4时，移动24-1=15次当n为5时，移动25-1=31次 从而合理推测：当n为k时，移动2k-1次当n等于64时，移动次数为264-1次16 按照汉诺塔的移动原则，将N个盘从A杆移动到C 杆需要移动盘的次数是 2 的 N 次幂减 1 ， 那么 64个盘移动次数就是184467445，近19亿亿次（且没有任何错误操作。这是一个天文数字，即使一台功能很强的现代计算机来解汉诺塔问题，恐怕也需要很长的时间，因此

7、要想得到结果，在运行程序时，输入的N可不能太大。据说布拉玛婆罗门圣庙的僧侣声称， 汉诺塔游戏结束就标志着世界末日的到来，现在看来确实是有道理的。因为如果每秒移动一次（且没有任何错误），64个盘则大约需近5800亿年，而据科学家以能源角度推算，太阳系的寿命只不过150 亿年而已。 173）分析及解答执行条件：只要n0(n是整数),我们就要执行。如果n为1(只有一个盘子)，很易办到，只要frompeg-topeg。把在A柱上(frompeg)上的n-1(n1)个盘子依规则从A(frompeg)柱移到B柱上(auxiliary/temppeg)可借助空柱C(to/topeg);把A柱上剩下的1个从A

8、(frompeg)移到C(topeg)；把B柱(auxiliary/temppeg)上的n-1个盘子借助A柱(frompeg)移到C柱(to/topeg)。函数可设计为：move_tower(盘个数，取出柱，放入柱，辅助柱)18以上三点为基本思想，则归纳的n个盘子的移动(n1)函数如下： move_tower(int disk_num, char from, char to , char aux); 注: from-frompeg to-topeg aux-auxiliary或temporary 它可以通过求move_tower(disk_num-1,from,aux,to);和mov_tower(disk_num-1,aux,to,from);来实现。19源程序如下：includevoid move_tower(int disk_num,char from,char to ,char aux) if(disk_num1) mov_tower(disk_num-1,from,aux,to); coutMove disk disk_numfromfromtotoendl; move_tower(disk_num-1,aux,to,from); else coutMove disk 1 fr