經(jīng)典遞歸問(wèn)題總結(jié)

   深入了解和掌握遞歸問(wèn)題是一個(gè)高效程序員的基本素養(yǎng)，無(wú)論在平時(shí)課程學(xué)習(xí)或者競(jìng)賽中，遞歸思想的地位舉足輕重，故在此對(duì)一些經(jīng)典遞歸問(wèn)題進(jìn)行一些總結(jié)。
(1)  計(jì)算一個(gè)數(shù)組中元素的累加和
#include<stdio.h>
 
intaddAll(int a[],int begin,int end);
intmain(){
int a[6]={3,5,1,6,34,67};
int sum=0;
//計(jì)算a數(shù)組的累加和
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)  比較兩個(gè)數(shù)組中元素是否完全相同
#include<stdio.h>
 
bool strcomp(char str1[],char str2[],int length,int begin);
intmain(){
charstr1[10]="hello",str2[10]="hewlo";
//比較兩個(gè)數(shù)組是否相同
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個(gè)球中取出m個(gè)，一共有多少可能性
 
#include<stdio.h>
 
intselect( int n,int m ); 
intmain(){
//從n個(gè)球中取出m個(gè)不同的球，一共有多少種可能性
 printf("從5個(gè)球里取出2個(gè)球的可能性: %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)  求兩個(gè)字符串的最大公共子序列
#include<stdio.h>
#include<math.h>
 
#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("兩個(gè)字符串的最大公共子序列為: %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項(xiàng)的元素
#include<stdio.h>

int yanghuiTriangle(int m,int n);
int main(){
 int m,n; //m為層數(shù)(從0開(kāi)始)，n為第n項(xiàng)(從0開(kāi)始)
 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)求兩個(gè)數(shù)的最小公倍數(shù)
#include<stdio.h>

int gcd(int a,int b);

int main(){
	int a=9,b=4;
	printf("a和b的最大公約數(shù)為:%d\n",gcd(a,b));
} 

int gcd(int a,int b){
	if(a==0) return b;  /*遞歸結(jié)束條件*/
	return gcd(b%a,a);
}
(7)遞歸求一個(gè)數(shù)的n次冪
#include<stdio.h>

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);
}