4.2 递归与预编译.ppt

4.2 递归与预编译 预编译处理 递归算法 宏替换（#define命令） §2 递归算法 能采用递归描述的算法通常有这样的特征： 为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在递推阶段，必须要有终止递归的情况。例如,当n为1或者0时的情况。 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。 递归算法举例 1、N！问题 2、Fabonacci问题 3、Hannoi塔问题 4、杨辉三角形问题 1、N！问题 N的阶乘为：n(n-1)(n-2)(n-3)……，即： 1!=1; 2!=2*1!; n!=n*(n-1)!（当n1时）。 写成递归函数有： int factorial(int n) { if (n==1) return 1; else return n*factorial(n-1); } 2、Fibonacci问题 斐波那契数列为：1、1、2、3、5、8、13……，即： fib(1)=1; fib(2)=1; fib(n)=fib(n-1)+fib(n-2) （当n2时）。 写成递归函数有： int fib(int n) { if (n=2) return 1; else return fib(n-1)+fib(n-2); } 3、汉诺（Hanoi）塔问题： 古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，编写一个程序，来求解移动的步骤。 这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。 如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。 如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。 这说明：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。 如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。 这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。 如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。 …… 上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。 void Move(char chSour, char chDest) /*打印移动步骤*/ { printf(\nMove the top plate of %c to %c,chSour, chDest); } Hanoi(int n, char chA, char chB, char chC) { /*检查当前的盘子数量是否为1*/ if(n==1) /*盘子数量为1，打印结果后，不再继续进行递归*/ Move(chA,chC); else /*盘子数量大于1，继续进行递归过程*/ { 源，借，目的 Hanoi(n-1,chA,chC,chB); Move(chA,chC); Hanoi(n-1,chB,chA,chC); } } main() { int n; /*输入盘子的数量*/ scanf(%d,n); printf(\nMoving %d plates from A to C:,n); /*调用函数计算，并打印输出结果*/ Hanoi(n,A,B,C); } 4、杨辉三角 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 …… …… …… …… yanghui(int i,int j) { if(j==1||i==j) return 1;