C++递归函数

C++递归函数

  

B.递归可以解决的问题：

阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解

C.递归的过程（图片来源见水印，侵删）

【递归的过程可以理解为，把一个复杂的问题转化为一个个的小问题，而小问题能转化为更简单的问题，直到达到递归的“终点”——递归边界。递归边界是递归问题的特殊案例或者简单的情况，通过递归边界向上一层一层的返回数据，结束递归】

D.递归实例

#include 
  
    using namespace std; int Leo(int n) { int sum = 1; if(1 == n)//递归终止条件 { return 1; } sum =n * Leo(n - 1); return sum;//返回阶乘的总和 } int main() { int num; cin >> num;//输入一个数 cout << Leo(num) << endl; //输出该数的阶乘 return 0; } /* *在求X的阶乘和时 *可以利用递归的思想 *把大问题转化成小问题 *再把小问题转化成更小的问题 *最后得解 */ 
  

 Example ②：//Fibonacci数列

//Fibonacci数列的第一项为0，第二项为1，后续的每一项是前两项的和 //该数列的前两项的比例趋于一个常量：1.168...，成为黄金分割 数列形如：0 1 1 2 3 5 8 13 21 34... #include 
  
    using namespace std; long int Leo(long int n); int main() {     long n;     cin>>n;//求Fibonacci数列的第n项     cout< 
    
  

Example ③：//全排列

//无重复元素的全排列

#include 
  
    using namespace std; int arr[5]={0,1,2,3,4}; int resove(int n)//递归函数 { if(n==5)//当尝试对不存在的数组元素进行递归时，标明所有数已经排列完成，输出。 { for(int i=0;i<5;i++) cout< 
    
  

10234  10243  10324  10342  10432  10423  12034  12043  12304  12340  12430  12403  13204  13240  13024  13042  13402  13420  14230  14203  14320  14302  14032  14023  

21034  21043  21304  21340  21430  21403  20134  20143  20314  20341  20431  20413  23014  23041  23104  23140  23410  23401  24031  24013  24301  24310  24130  24103  

31204  31240  31024  31042  31402  31420  32104  32140  32014  32041  32401  32410  30214  30241  30124  30142  30412  30421  34201  34210  34021  34012  34102  34120  

41230  41203  41320  41302  41032  41023  42130  42103  42310  42301  42031  42013  43210  43201  43120  43102  43012  43021  40231  40213  40321  40312  40132  40123

//全排列算法模板 

void permutation1(char* str,int sbegin,int send) //全排列的非去重递归算法 { if( sbegin == send) //当 sbegin = send时输出 { for(int i = 0;i <= send; i++) //输出一个排列 cout << str[i]; cout << endl; } else { for(int i = sbegin; i <= send; i++) //循环实现交换和sbegin + 1之后的全排列 { swap(str[i],str[sbegin]); //把第i个和第sbegin进行交换 permutation1(str,sbegin + 1,send); swap(str[i],str[sbegin]); //交换回来 } } } 

//有重复元素的全排列

【去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换】

#include 
  
    using namespace std; int sum=0;//记录有多少种组合 void Swap(char str[], int a, int b) { char temp = str[a]; str[a] = str[b]; str[b] = temp; } bool IsSwap(char *pchar, int nBegin, int nEnd)//判断字符是否相同 { for (int i = nBegin; i < nEnd; i++) if (pchar[i] == pchar[nEnd]) return false; return true; } void Perm(char str[], int begin, int end) { if (begin==end) { for (int i = 0; i <= end; i++) { cout << str[i]; } cout << endl; sum++; return; } else { for (int j = begin; j <=end; j++) { if (IsSwap(str, begin, j))//如果不相同 进行交换 { Swap(str, begin, j); Perm(str, begin + 1, end); Swap(str, j, begin); } } } } int main() { int n; char c[16]; char tmp; cin >> n; tmp = getchar(); // 接受回车 if (1 <= n && n <= 15){ for (int i = 0; i < n; i++){ c[i] = getchar(); } Perm(c, 0, n - 1); } cout << sum; cout << endl; return 0; } 
  

有重复元素的全排列问题的关键就是要先判断是否是和后面的元素重复，如果不重复在进行交换

Example ④：//递归实现二分查找

#include 
  
    #define MAX_SIZE 102 using namespace std; template 
   
     //类模板 int BinarySearch(T a[],const T&x,int n,int left,int right) { if(left>=right) return -1; else { if(a[(left+right)/2]==x) return (left+right)/2; else if(x>=(left+right)/2) return BinarySearch(a,x,n,(left+right)/2+1,right); else if(x<(left+right)/2) return BinarySearch(a,x,n,left,(left+right)/2-1); } } int main() { int a[MAX_SIZE]; int i,len,x,p; cin>>len;//输入数组长度 for(i=0;i 
    
      >a[i]; cin>>x;//输入要查找的数 p=BinarySearch(a,x,len,0,len-1); if(p==-1) cout<<"该数不存在！"< 
                 

E.递归例题

题目代码及分析

#include 
   
     using namespace std; int sum;//全局变量 方便在count函数中使用sum void count(int a,int b) { for(int i=a;i 
    
      b/i) break; } } int main() { int n; int a; //被分解的数 cin >> n; //数据组数 while(n) { sum = 1; cin >> a; count(2,a); cout< 
      
     
   

题目代码及分析

#include 
    
      using namespace std; int main(){ int n; cin>>n; int m=0; for(int a2=n;a2>=0;a2--){//从n开始 依次向前遍历 for(int a3=n;a3>=0;a3--){ if((a2+a3)%3==0){ for(int a1=n;a1>=0;a1--){ if(((a1+a2+a3)%5==0) && ((a1+a2)%2==0)){ m=max(m,a1+a2+a3);//求出最大值 输出 } } } } } cout< 
      
    

F.心得体会