运用递归解决问题的要点：
（1）缩小问题规模（将问题分为若干步，注意构造问题间的相似性）
（2）分析递归出口
下面从一些经典的实例来分析递归问题的特征
1.从n个小球中取m个，问有多少种取法？
1 #include <iostream> 2 using namespace std; 3 4 int f(int n,int m){ 5 if(n<m) return 0; 6 if(m==0) return 1; 7 return f(n-1,m)+f(n-1,m-1); 8 } 9 int main(){ 10 int n,m; 11 cin>>n>>m; 12 cout<<f(n,m); 13 }
2.打印字符串的全排列
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 using namespace std; 5 6 void f(string str,int k) 7 { 8 if(str.length()-1==k){ 9 cout<<str<<endl; 10 return; 11 } 12 for(int i=k;i<str.length();i++){ 13 swap(str[k],str[i]); 14 f(str,k+1); 15 swap(str[k],str[i]); 16 } 17 } 18 int main() 19 { 20 string str="abc"; 21 f(str,0); 22 return 0; 23 }
3.最长公共子序列的长度
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 string a,b; 7 int lcs(int m,int n) 8 { 9 if(m==-1||n==-1) return 0; 10 if(a[m]==b[n]) return lcs(m-1,n-1)+1; 11 else return max(lcs(m-1,n),lcs(m,n-1)); 12 } 13 int main(){ 14 cin>>a>>b; 15 cout<<lcs(a.length()-1,b.length()-1)<<endl; 16 }
转载于:https://www.cnblogs.com/kirito61/p/7172332.html
