递归二

• 递归不仅包括函数直接调用自身，还可以多函数互相调用，形成间接调用

  eg.求表达式的值

  # include<iostream>
  using namespace std;
  //因为要相互调用，所以要提前声明
  double expression_value();
  double factor_value();
  double term_value();
  
  double expression_value(){
      double result = term_value();
      //保证把所有的项都读到；所以用一个while循环，里面没必要用while用了不知道为什么是错的
      while(true){
          //cin.peek()是从输入流里看一看，而不取走这个字符
          char op = cin.peek();
          if(op=='+') {
              getchar();
              result += term_value();
          }
          if(op=='-') {
              getchar();
              result -= term_value();
          }
          else if(op != '+' && op!='-'){
              break;
          }
      }
      return result;
  }
  
  double term_value(){
      double result = factor_value();
      while(true){
          char ch = cin.peek();
          if(ch == '*'){
              getchar();
              result *= factor_value();
          }
          if(ch=='/'){
              getchar();
              result /= factor_value();
          }
          else if(ch != '*'&&ch != '/'){
             break;
          }
      }
      return result;
  }
  
  double factor_value(){
      double result = 0;
      char ch = cin.peek();
      if(ch == '('){
          getchar();
          result = expression_value();
          getchar();
      }else{
          while(isdigit(ch)){
              //isdigit()是判断是不是数字
              result = result*10 + ch-'0';
              cin.get();
              ch = cin.peek();
          }
      }
      return result;
  }
  
  int main(){
      //其实整个读入输入的过程都是在factor_value里面进行的
      cout << expression_value() << endl;
  }
  

• 递推公式的问题——注意边界情况

  爬楼梯：

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

  放苹果——m个苹果放到n个盘子里

# include<iostream>
using namespace std;
int f(int m,int n){
    if(n>m) return f(m,m);
    //0个剩余，说明有了一种放法C_n ^0 =1
    if(m == 0) return 1;
    if(n == 0) return 0;
    //有空盘+无空盘
    return f(m-n,n) + f(m,n-1);
}
int main(){
    int m,n;
    cin >> m,n;
    cout << f(m,n);
}

算24

输入5个整数，计算他们能否通过四则运算得到24；

# include<iostream>
# include<cmath>
//double没有==
# define EPS 1e-8

using namespace std;
int comput_24(double a[],int len){
    //终止条件
    if(len == 1){
        if(fabs(a[0]-24) < EPS) return 1;
    }else if(len == 1){
        return 0;
    }
    double temp[6];
    //其实还是枚举
    for(int i = 0;i<len-1;i++){
        for(int j = i+1;j<len;j++){
            //p用来指示b中有多少数
            int p = 0;
            //  把不参与四则运算的 放到temp里面
            for(int k= 0;k<len;k++){
                if(k != i && k != j){
                    temp[p] = a[k];
                    p++;
                }
            }
            //下面注意，加法和乘法有交换律，除法和减法没有
            temp[p] = a[i]+a[j];
            if(comput_24(temp,p+1) ){
                return true;
            }
            temp[p] = a[i]*a[j];
            if(comput_24(temp,p+1) ){
                return true;
            }
            if(a[i] != 0){
                temp[p] = a[j]/a[i];
                if(comput_24(temp,p+1) ){
                    return true;
                }
            }
            //而且除法还要注意，分母不为零
            if(a[j] != 0){
                temp[p] = a[i]/a[j];
                if(comput_24(temp,p+1) ){
                    return true;
                }
            }
            temp[p] = a[i]-a[j];
            if(comput_24(temp,p+1) ){
                return true;
            }
            temp[p] = a[j]-a[i];
            if(comput_24(temp,p+1) ){
                return true;
            }
        }
    }
    return false;
}
int main(){
    double a[5];
    //int b[5];
    for(int i = 0;i<5;i++){
        cin >> a[i];
    }
    cout << comput_24(a,5);
}