十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
深入了解和掌握递归问题是一个高效程序员的基本素养,无论在平时课程学习或者竞赛中,递归思想的地位举足轻重,故在此对一些经典递归问题进行一些总结。 (1) 计算一个数组中元素的累加和 #includeintaddAll(int a[],int begin,int end); intmain(){ int a[6]={3,5,1,6,34,67}; int sum=0; //计算a数组的累加和 sum=addAll(a,0,5); printf("%d\n",sum); } intaddAll(int a[],int begin,int end){ if(begin==end){ return a[begin]; } int mid=(begin+end)/2; intsum=addAll(a,begin,mid)+addAll(a,mid+1,end); return sum; } (2) 比较两个数组中元素是否完全相同 #include bool strcomp(char str1[],char str2[],int length,int begin); intmain(){ charstr1[10]="hello",str2[10]="hewlo"; //比较两个数组是否相同 printf("%d\n",strcomp(str1,str2,5,0)); } boolstrcomp(char str1[],char str2[],int length,int begin){ if(begin==length){ return true; }else{ if(str1[begin]!=str2[begin]){ return false; } returnstrcomp(str1,str2,length,begin+1); } } (3) 从n个球中取出m个,一共有多少可能性 #include intselect( int n,int m ); intmain(){ //从n个球中取出m个不同的球,一共有多少种可能性 printf("从5个球里取出2个球的可能性: %d\n",select(5,2)); } intselect( int n,int m ){ if(m==0){ return 1; } if(m>n){ return 0; } if(n==m){ return 1; } return select(n-1,m-1)+select(n-1,m); } (4) 求两个字符串的最大公共子序列 #include #include #define N100 intmaxSubsequence(char str1[],char str2[],int begin1,int begin2); intmax(int a,int b); intmain(){ char str1[N]; char str2[N]; int max; scanf("%s %s",str1,str2); max=maxSubsequence(str1,str2,0,0); printf("两个字符串的最大公共子序列为: %d\n",max); return 0; } intmaxSubsequence(char str1[],char str2[],int begin1,int begin2){ if(str1[begin1]=='\0' || str2[begin2]=='\0'){ return 0; } if(str1[begin1]==str2[begin2]){ returnmaxSubsequence(str1,str2,begin1+1,begin2+1)+1; }else{ return max(maxSubsequence(str1,str2,begin1+1,begin2),maxSubsequence(str1,str2,begin1,begin2+1)); } } intmax(int a,int b){ return a>b?a:b; } (5)杨辉三角求第m层第n项的元素 #include int yanghuiTriangle(int m,int n); int main(){ int m,n; //m为层数(从0开始),n为第n项(从0开始) int value; scanf("%d %d",&m ,&n); value=yanghuiTriangle(m,n); printf("%d",value); } int yanghuiTriangle(int m,int n){ if(m==0) return 1; if(n==0) return 1; if(n==m) return 1; if(n>m) return -1; return yanghuiTriangle(m-1,n-1)+yanghuiTriangle(m-1,n); } (6)求两个数的最小公倍数 #include int gcd(int a,int b); int main(){ int a=9,b=4; printf("a和b的最大公约数为:%d\n",gcd(a,b)); } int gcd(int a,int b){ if(a==0) return b; /*递归结束条件*/ return gcd(b%a,a); } (7)递归求一个数的n次幂 #include long long pow(int a,int b); int main(){ int a=3,b=3; printf("%d的%d次幂为:%d\n",a,b,pow(a,b)); } long long pow(int a,int b){ if(b%2==1) return a*pow(a,b-1); if(b==0) return 1; return pow(a*a,b/2); }