5 函数(递归部分).pptVIP

提纲 递归的概念 递归过程 递归程序设计 1.递归的概念 例：编写一个函数fac，计算阶乘n! 按过去的设计思想，该函数可以写成： int fac(int n) { int i,p; p=1; for(i=2;i=n;i++) p=p*i; return p; } 1.递归的概念 现在换一个角度考虑，n！不仅是1×2×3×…×n, 还可以定义成： 递归的定义： 从程序书写来看，在定义一个函数时，若在定义它的内部又出现对它本身的调用，则称该函数是递归的或递归定义的。 从函数动态运行来看，当调用一个函数A时，在进入函数A且还没有退出（返回）之前，又再一次由于调用A本身而再一次进入函数A，则称之为函数A的递归调用。 1.递归的概念 例2：求x的n次幂。函数 可定义如下： 1.递归的概念 递归可以分为直接递归和间接递归两种。 直接递归：函数体里面发生对自己的调用； 间接递归：函数A调用函数B，而函数B又直接或间接地调用函数A。 2.递归过程 求f（6）的 递归调用过程？ 2.递归过程 2.递归过程 可见，递归算法的执行过程分递推和回归两个阶段。 当递推时，并没有求值的计算操作，实际的计算操作是在回归过程实现的。 递推阶段是个不断简化问题的阶段：把对较复杂问题（规模为n）的求解转化为比原问题简单一些的问题（规模小于n）的求解 。例如对fib(6)的求解转化为fib(5)的求解， 对fib(5)的求解转化为fib(4)的求解…直到转化为对fib(0)的求解。 当递推到最简单的不用再简化的问题时，递推终止。如f函数中，n＝0的情况。 2.递归过程 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解 。如在得到f(1)的解后，又依次得到f(2)、f(3)…直到f(6)的值。 3.递归程序设计 什么样的问题可以用递归解决？ 如果解决问题的方法是把该问题分解成小的子问题，并且这些小的子问题可以用同样的算法解决，当分解到可以解决的比较简单的子问题时分解过程即终止，那么就可以用递归。 递归的思想就是将一个问题先转化为与原问题性质相同、但规模小一级的新问题，然后再重复这样的转化，直到问题的规模减小到我们很容易解决为止。 3.递归程序设计 例3：用函数fib求斐波那契数列的第n项。斐波那契数列为：0、1、1、2、3、…… 。函数fib定义如下： 3.递归程序设计 每求一项数，需要递归调用2次该函数；计算斐波那契数列第30项的递归调用次数是2的30次方（大约10亿次！） 可见递归的思想特别符合人们的思维习惯，便于问题解决和编程实现。但递归的程序设计方法比较占用系统资源，效率也较低。 课下请改写fib函数，该用非递归方式实现 long fib(long), 计算斐波那契数列第n项。 三、递归问题举例 一、汉诺塔问题 1、问题分析（为简单起见，假设A柱上只有6个盘子） 很显然这是一种递归解法。它将问题分解成若干同样类型的小问题，移动一个盘子的简单操作就是终止条件。 将n个圆盘从A柱移到C柱的递归解法： 1.将A柱上面的从上往下数的（n－1）个圆盘移到B柱上，中间通过C柱为辅助。这是一个（n－1）个圆盘的问题； 2. 将A柱上的最后一个圆盘，直接移到C柱上； 3.再将B柱上的（n－1）个圆盘移到C柱上，中间以A柱为辅助。这又是一个（n－1）个圆盘的问题。 以上步骤将移动n个圆盘的问题转化为移动（n－1）个圆盘的问题。同理，我们可以继续把（n－1）个圆盘的问题转化为（n－2）个圆盘的问题，……，直到最后变成1个圆盘的问题，这时候，问题就很容易解决了（直接移动就可以了）。 void move(int n, int a, int b, int c) { if (n==1) printf(“ %d--%d \n, a, c); else{ move(n-1, a, c, b); printf(“ %d--%d \n, a, c); move(n-1, b, a, c); } } 主函数部分： #includestdio.h void move(int n,int a,int b,int c); main() { int num； printf(the number of plate is:); scanf(%d,num); move(num, 1, 2, 3); system(“pause”); retrun 0; } 移动三个盘子的运行结果运行结果 t