VB函数递归与调用-1.ppt

函数的递归调用  函数的递归调用 递归: 一个函数直接或间接地使用自身。 1. 直接递归调用：函数直接调用本身 2. 间接递归调用：函数间接调用本身 分析：要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。第一个人的年龄已知，根据第一个人的年龄可依次求得第二、三、四、五个人的年龄。这就是一个递归问题。 而每一个人的年龄都比其前1个人的年龄大2 就是递归成立的条件，也就是递归公式。 age（5）=age（4）＋2 age（4）=age（3）＋2 age（3）=age (2）+2 age（2）＝age(1）＋2 age（1）＝10 可以用式子表述如下： age（n）=10 （n=1） age（n）= age（n-1)+2 （n＞1） 可以看到，当n＞1时，求第n个人的年龄的公式是相同的。因此可以用一个函数来表示上述关系，下图表示求第5个人年龄的过程。 可以用一个函数来描述上述递归过程： age（n） /*求年龄的递归函数*／ int n； ｛int c； ／* c用来存放函数的返回值 if（n= =1） c=10; else c=age（n一1）十2； return（c)； } main（）/*主函数*／ {printf（%d，age（5））；} 例题二 用递归方法求n! 分析：假设n=5 我们知道 5！=1*2*3*4*5=4！*5 4！=1*2*3*4=3！*4 3！=1*2*3=2！*3 2！=1*2=1！*2 1！=1 可用下面的递归公式表示 n!=1 （n=1） n!=(n-1)!*n (n 1) 递归法求Fibonacci数列 Fibonacci数列: 1, 1, 2, 3, 5, 8, 13… 迭代法求Fibonacci数列的前20项 #include stdio.h void main( ) { int i , f1=1 , f2=1 , f3; printf(“%8d%8d”, f1 , f2); for ( i=3 ; i=20 ; i++ ) { f3=f1+f2; f1=f2; f2=f3; printf(“%8d”, f3); if ( i%4==0) putchar(‘\n’); } } 讨论：汉诺塔问题属于非数值问题，难以用数学公式表达其算法，可以从分析问题本身的规律入手。 第一步，问题化简，设A针上只有一个盘子，即n=1，则只需将1号盘从A针移到C针。 第二步，问题分解，对于有n（n1）个盘子的汉诺塔，可分为三个步骤求解： 1.将A针上n-1个盘子借助于C针移到B针 2.把A针上剩下的一个盘子移到C针 3.将B针上n-1个盘子借助于A针移到C针 显然，上述1,3两步具有与原问题相同的性质，只是在问题的规模上比原问题有所缩小，可用递归实现。 整理上述分析结果，把第一步作为递归结束条件，将第二步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述： 定义一个函数movedisk (int n,char fromneedle ,char tempneedle , char toneedle )，该函数的功能是将fromneedle针上的n个盘子借助于tempneedle针移动到toneedlee针，这样移动n个盘子的递归算法描述如下： movedisk(int n,char fromneedle,char