递归一

• 递归可以解决的问题
• 代替多重循环
• 解决循环次数不确定的问题
• 解决递归定义的问题
• 将问题分解为更小规模的子问题

• eg1.求阶乘

  # include<iostream>
  using namespace std;
  int Jiecheng(int n){
      if (n == 0){
          return 1;
      }
      return n*Jiecheng(n-1);
  }
  int main{
      int n;
      cin >> n;
      cout << Jiecheng(n);
  }
  
  

• eg2.汉诺塔问题

  # include <iostream>
  using namespace std;
  void Hanoi(int n,char src,char mid,char std){
      if(n==1){
          cout << src << " --> " << std;
      }
      Hanoi(n-1,src,std,mid);
      cout << src << " --> " << std;
      Hanoi(n-1,mid,src,std);
  }
  int main(){
      int n;
      cin >> n;
      Hanoi(n,'A','B','C');
  }
  

• eg3.n皇后问题

  #include <iostream>
  #include <cstdlib>
  using namespace std;
  //n 皇后
  int N;
  int QueenPole[100];
  //求第n行的皇后位置，当n== N时，输出QueenPole（序号<N）
  void nQueen(int n){
      if(n == N){
          for(int i= 0;i<n;i++){
              cout << QueenPole[i]+1 << ends;
          }
          cout << endl;
      }
      //求第n行的皇后,枚举第n行皇后所有可能的位置
      int possible;
      for(possible = 0;possible<N;possible++){
          int before;
          for(before = 0;before < n;before++){
              if(QueenPole[before] == possible || abs(n - before) == abs(possible - QueenPole[before]))
                  break;
          }if(before == n){
              QueenPole[n] = possible;
              nQueen(n+1);
          }
      }
  
  }
  int main() {
      cin >> N;
      nQueen(0);
  }
   
  

abs 求绝对值函数好像在n多头文件里都有<cmath>,<cstdlib>

• eg4逆波兰表达式

  #include <iostream>
  #include <cstdlib>
  using namespace std;
  double expression_value(){
      char s[20];
      cin >> s;
      switch (s[0]){
          case '*':return expression_value()*expression_value();
          case '/':return expression_value()/expression_value();
          case '+':return expression_value()+expression_value();
          case '-':return expression_value()-expression_value();
          default:return atof(s); // atof(string *)把字符串装换成浮点型 auto_float
      }
  }
  int main(){
      cout << expression_value();
  }