关于递归算法的研读及体会.doc

关于递归算法的研读及体会 递归式定义 递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。主要有三种解递归式的方法：代换法、递归树方法、主方法。 算法思想 对于一个复杂的问题，把原问题分解为若干个相对简单的同类型的子问题，继续下去直到子问题简单到能够直接求解，也就是说找到了递推的出口，这样原问题就由递推得解。 算法特点 递归就是在过程或函数里调用自身。 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 递归算法解题通常显得很简洁，但递归算法解题的运行效率很低。所以一般不提倡用递归算法设计程序。 在递归调用的过程中，系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。 算法要求 递归算法所体现的“重复”一般有三个要求： 每次调用在规模上都有所缩小（通常是减半）； 相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）； 问题的规模极小时必须要直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的，无条件的递归调用将会成为死循环而不能正常结束。 关键要抓住的是： 递归出口 递归条件 递推逐步向出口逼近 图1-1 递归算法流程图 算法示例 一、Fibonacci数列 问题1. 调用递归算法求Fibonaccis数列的前m项并输出。 Fibonaccis数列：1 1 2 3 5 8……，该数列的规律为，前两项的值为1，从第三项开始，每一项是前两项的和。 解： #includestdio.h int fib(int m) { int f; if(m==1||m==2) //递推出口 f=1; else f=fib(m-1)+fib(m-2); //递归调用 return f; } void main() { int m,i; printf(请输入要输出的数的个数：); scanf(%d,m); printf(输出的%d项fibonacci数列为：\n,m); for(i=1;i=m;i++) { printf(%-6d,fib(i)); if(i%8==0){printf(\n);} } printf(\n); } 结果如下： 图1-2 一-问题1结果运行图 问题2. 从n人中任取k人的方法数。 解： #includestdio.h int fun(int n,int k) { if(kn) return 0; else if(n==k||k==0) return 1; else return fun(n-1,k)+fun(n-1,k-1); } void main() { int n,k,result; scanf(%d%d,n,k); result=fun(n,k); printf(从%d个人里取%d个人有%d种取法\n,n,k,result); } 结果如下： 图1-3 一-问题2结果运行图 二、扑克牌问题 问题1. 从52张扑克牌中取出3张黑桃，2张红桃的方法数 解： #includestdio.h int fun(int n,int k) { if(kn) return 0; else if(n==k||k==0) return 1; else return fun(n-1,k)+fun(n-1,k-1); //递推 } void main() { int result; float p; result=fun(13,3)*fun(13,2); p=1.0*result/fun(52,5); printf(从52张扑克牌中抽取3张黑桃，2张红桃总共有%d种情况，\n其概率为%f\n,result,p); } 结果如下： 图1-4 二-问题1结果运行图 问题2. 从52张扑克牌中取出至少3张红桃的方法数 解： #includestdio.h int fun(int n,int k) { if(kn) return 0; else if(n==k||k==0) return 1; else return fun(n-1,k)+fun(n-1,k-1); } void main() { int i,j,m; int sum=0; double result; for(i=1;i=13;i++) { printf(抽取%d张红桃有%d种情况\n,i,fun(13,i)); } for(j=3;j=13;j++) { sum+=fun(13,j); if(j==13){ printf(则至少有3张红桃共有%d种情况。\n,sum