“递归”，你真的掌握了吗？

递归

• 基本概念：一个函数调用其自身，就是递归
• 递归和普通函数调用一样，是通过栈实现的
• 递归的作用（适用情况）
  • 替代多重循环
  • 解决本来就是用递归形式定义的问题
  • 将问题分解为规模更小的子问题进行求解
• 两个要素
  • 如何将一个大规模问题分解为许多小规模问题，并且解决问题的形式、方法是一样的
  • 递归的终止条件

基本例题

case 1：阶乘问题

**问题描述：**求整数 $n$n 的阶乘

• **解题思路：**可以考虑使用循环，但本题采用递归手段解决。将 $n$n 的阶乘分解为 $n*(n-1)$n∗(n−1)的阶乘，接着将 $(n-1)$(n−1)的阶乘分解为 $(n-1)*(n-2)$(n−1)∗(n−2)的阶乘…以此类推，直到达到终止条件：$0$0 的阶乘为 $1$1

• 示例代码

  #include <iostream>
  using namespace std;
  
  int Factorial(int n) {
  	if (n == 0) {
  		return 1;
  	} else {
  		return n * Factorial(n-1);
  	}
  } 
  
  int main() {
  	int n;
  	cin>>n;
  	cout<<n<<"的阶乘为 : "<<Factorial(n)<<endl;
  	return 0;
  } 
  

case 2：汉诺塔问题

**问题描述：**有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？汉诺塔示意图如下

• **阶梯思路：**首先可以将问题进行如下分解：先把 $n-1$n−1 个盘子移动到 $B$B 杆，再把 剩下的最后一个盘子移动到 $C$C 杆，最后将 $B$B 杆的 $n-1$n−1 个盘子移动到 $C$C 杆。

  • 终止条件：如果 $A$A 杆有1个盘子，直接移动到 $C$C 杆即可。

• 示例代码

  #include <iostream>
  using namespace std;
  
  void Hanoi(int n, char src, char mid, char dest) {
  	// 将src座上的n个盘子，以mid为中转，移动到dest座
  	if (n == 1) {	// 只需移动一个盘子 
  		cout << src <<"->" << dest << endl;		// 直接将盘子从src移动到dest即可
  		return ;	// 递归终止 
  	} 
  	
  	Hanoi(n-1, src, dest, mid);		// 先将 n-1 个盘子从src移动到mid
  	cout << src <<"->" << dest << endl;	// 再将一个盘子从src移动到dest
  	Hanoi(n-1, mid, src, dest);		// 最后将 n-1 个盘子从mid移动到dest
  	return ; 
  } 
  int main() {
  	int n;
  	cin >> n;	// 输入盘子的数目
  	Hanoi(n, 'A', 'B', 'C');
  	return 0; 
  }
  

case 3：N 皇后

**问题描述：**输入整数 $n$n，要求 $n$n 个国际象棋的皇后，摆在 $n*n$n∗n 的棋盘上，互相不能攻击，输出全部方案。输出结果里的每一行都代表一种摆法，行里的第 $i$i 个数字如果是 $n$n ，就代表第 $i$i 行的皇后应该摆放在第 $n$n 列。

• 递归适用情况：替代多重循环

• 解题思路：由于不知道具体的 $n$n 是多少，循环的重数不确定，因此无法采用多重循环来实现， 本题采用递归的方法实现。

  • 核心思想：在摆放第 $k$k 行及其后的皇后时，假设第 $0$0~$k-1$k−1 行皇后已经摆放好
  • 终止条件：$k=n$k=n

• 示例代码：

  #include <iostream>
  #include <cmath>
  using namespace std;
  int N;
  int queenPos[100];	// 用来存放算好的皇后的位置。左上角是(0,0)
  void NQueen(int k);
  
  int main() {
  	cin>>N;
  	NQueen(0);	// 从第 0 行开始摆放皇后 
  	return 0;
  } 
  
  // 在 0~k-1 行皇后已经摆好的情况下，摆放 k 行及其后的皇后 
  void NQueen(int k) {
  	int i;
  	if(k == N) {
  		for(i=0; i<N; i++) {
  			cout << queenPos[i] + 1 << " ";
  		}
  		cout << endl;
  		return ;
  	} 
  	for(i=0; i<N; i++) {
  		int j;
  		for(j=0; j<k; j++) {
  			// 和已经摆好的 k 个皇后的位置比较，看是否冲突
  			if(queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j)) {
  				break;	// 冲突，则试下一个位置 
  			} 
  		}
  		if(j == k) {	// 当前选的位置 i 不冲突 
  			queenPos[k] = i;	// 将第 k 个皇后摆放在位置 i 
  			NQueen(k+1);
  		}
  	}
  } 
  

• 代码细节详情

  • NQueen(int k)函数：在 $0$0~$k-1$k−1 行皇后已经摆好的情况下，摆放 k 行及其后的皇后
  • abs(queenPos[j] - i) == abs(k - j)：处理位于对角线的情况，行号之差等于列号之差

case 4：逆波兰表达式

**问题描述：**逆波兰表达式是一种把运算符前置的算数表达式，例如普通的表达式 $2+3$2+3 的逆波兰表达式法为 $+\space 2 \space 3$+ 2 3 。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如$(2+3)*4$(2+3)∗4的逆波兰表示法为$* \space + \space 2\space 3\space 4$∗ + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括$+\space -\space *\space /$+ − ∗ / 四个。

• 递归适用情况：问题本身就是递归形式

• 逆波兰表达式的定义

  • 一个数是逆波兰表达式，值为该数
  • “运算符 逆波兰表达式 逆波兰表达式” 是逆波兰表达式，值为两个逆波兰表达式的值运算结果

  由以上特性发现该问题是一个递归形式的问题，故用递归解决

• **解题思路：**分别提取运算符后面的两个逆波兰表达式，递归求解问题

• 示例代码：

  #include <iostream>
  #include <cstdio>
  #include <cstdlib>
  using namespace std;
  
  double exp() {
  	// 读入一个逆波兰表达式，并且计算其值 
  	char s[20];
  	cin >> s;
  	switch(s[0]) {
  		case '+': return exp() + exp();		// 分别读取 + 号后面的两个逆波兰表达式，将其相加即可 
  		case '-': return exp() - exp();
  		case '*': return exp() * exp();
  		case '/': return exp() / exp(); 
  		default : return atof(s);
  		// atof() : 把一个字符串类型的浮点数转换double类型的 
  		break; 
  	} 
  }
  
  int main() {
  	printf("%lf", exp());
  	return 0;
  }
  

case 5：表达式求值

**问题描述：**输入为四则表达式， 仅由数字、$+、-、*、/、(、)$+、−、∗、/、(、)组成，没有空格，要求求其值。假设运算符结果都是整数、“/”结果也是整数

• 递归适用情况：问题本身就是递归问题

• 表达式是一个递归的定义

  表达式	项	因子

  • 由以上定义可以看出，表达式要用到项的定义，项要用到因子的定义，因子要用到表达式的定义，是一个递归的过程（间接的递归）
  • 终止条件：单个的整数就是因子

• 示例代码

  #include <iostream>
  #include <cstring>
  #include <cstdlib>
  using namespace std;
  int factor_value();		// 读入一个因子并返回其值
  int term_value();		// 读入一项并返回其值
  int expression_value();	// 读入一个表达式并返回其值
  
  int main() {
  	cout<<expression_value()<<endl;
  	return 0;
  }
  
  int expression_value() {	// 求一个表达式的值 
  	int result = term_value();	// 求第一项的值
  	bool more = true;
  	while(more) {
  		char op = cin.peek();	// 从输入流中看一个字符，不取走
  		if (op == '+' || op == '-') {
  			cin.get();	// 从输入中取走一个字符
  			int value = term_value();
  			if(op == '+') {
  				result += value;
  			}  else {
  				result -= value;
  			}
  		} else {
  			more = false;
  		}
  	}
  	return result; 
  }
  
  int term_value() {	//求一个项的值
  	int result = factor_value();	// 求第一个因子的值
  	while(true) {
  		char op = cin.peek();
  		if (op == '*' || op == '/') {
  			cin.get();
  			int value = factor_value();
  			if (op == '*') {
  				result *= value;
  			} else {
  				result /= value;
  			}
  		} else {
  			break;
  		}
  	} 
  	return result;
  } 
  
  int factor_value() {
  	int result = 0;
  	char c = cin.peek();
  	if (c == '(') {
  		cin.get();		// 拿走左括号
  		result = expression_value();	// 计算括号中表达式的值
  		cin.get();		// 拿走右括号 
  	} else {
  		while (isdigit(c)) {
  			result = 10 * result + c - '0';
  			cin.get();
  			c = cin.peek();  
  		}
  	} 
  	return result;
  }
  

• 代码细节详情

  • 注意三个函数factor_value()、term_value()、expression_value()之间的相互调用（根据定义图的关系）
  • cin.peek()：看一个字符，不取走
  • cin.get()：取走一个字符

case 6：上台阶

**问题描述：**树老师爬楼梯，他可以每次走$1$1级或者$2$2级，输入楼梯的级数，求不同的走法数。例如：楼梯一种有$3$3级，他可以每次都走 一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，共有$3$3种方法。

• 递归适用情况：将问题分解为规模更小的子问题进行求解

• 求解思路：$n$n 级台阶的走法 $=$= 先走一级后，$n-1$n−1 级台阶的走法 + 先走两级后，$n-2$n−2 级台阶的走法，抽象为数学表达式为：$f(n)=f(n-2)+f(n-2)$f(n)=f(n−2)+f(n−2)

  • 边界条件：边界条件有多种选择方案，只要达成目的即可，本题的边界条件有如下
    $\begin{cases} n<0,\quad return\space 0 \\ n=0,\quad return \space 1 \end{cases} 或 \begin{cases} n=0,\quad return\space 1 \\ n=1,\quad return \space 1 \end{cases} 或 \begin{cases} n=1,\quad return\space 1 \\ n=2,\quad return \space 2 \end{cases}${n<0,return 0n=0,return 1​或{n=0,return 1n=1,return 1​或{n=1,return 1n=2,return 2​

• 示例代码

  #include <iostream>
  using namespace std;
  int N;
  int stairs(int n) {
  	if (n < 0) {
  		return 0;
  	}
  	if (n == 0) {
  		return 1;
  	}
  	return stairs(n-1) + stairs(n-2); 
  } 
  int main() {
  	while(cin >> N) {
  		cout << N <<" 级台阶共有 " << stairs(N) <<" 种走法"<<endl; 
  	}
  	return 0;
  }
  

case 7：放苹果

**问题描述：**把 $M$M 个同样的苹果放在 $N$N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

**输入：**第一行是测试数据的数目 $t (0\leq t\leq 20)$t(0≤t≤20)。以下每行均包含两个整数 $M$M 和 $N$N，以空格分开。$1\leq M,N\leq10$1≤M,N≤10。

**输出：**对输入的每组数据 $M$M 和 $N$N ，用一行输出相应的 $K$K

• **求解思路：**本题的问题规模较小，可以采用递归的方法求解，如若$M$M和$N$N的值较大，则递归会进行大量的重复计算，需采用动态规划。采用递归方法求解可以简单进行如下两种分类：

  • $N>M$N>M，即盘子数目大于苹果数目，此时必然要有$N-M$N−M个盘子空着，问题等效于将$M$M个苹果放在$M$M个盘子中，$f(m,n)=f(m,m)$f(m,n)=f(m,m)
  • $N<M$N<M，及苹果数目大于盘子数目：此时总情况 $f(m,n)$f(m,n) 可以等效为有盘子空着和无盘子空着两种子情况之和
    • 有盘子空着，即先拿走一个盘子，将$M$M个苹果放在剩余的$N-1$N−1个盘子中，$f(m,n-1)$f(m,n−1)
    • 无盘子空着，将所有的盘子中先放一个苹果，确保没有盘子是空着的，再将剩余的$M-N$M−N个苹果放在$N$N个盘子中，$f(m-n,n)$f(m−n,n)
  • 边界条件
    • $M=0$M=0，没有苹果时：此时只有一种放法，即所有盘子里都不放苹果，return 1
    • $N=0$N=0，没有盘子时：此时找不到放苹果的办法，return 0

• 示例代码

  #include <iostream>
  using namespace std;
  
  // m:苹果数目 n:盘子数目 
  int f(int m, int n) {
  	if(n > m) {			// 盘子数目 > 苹果数目 
  		return f(m,m);
  	} 
  	if(m == 0) {		// 苹果数目为 0 
  		return 1;
  	}
  	if(n == 0) {		// 盘子数目为 0 
  		return 0;
  	}
  	return f(m, n-1) + f(m-n,n);
  }
  
  int main() {
  	int t, m, n;
  	cin>>t;
  	while(t--) {
  		cin >> m >> n;
  		cout << f(m,n) << endl;
  	}
  	return 0;
  }
  

case 8：算 24

**问题描述：**给出$4$4个小于$10$10的正整数，你可以使用加减乘除$4$4种运算以及括号把这$4$4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于$24$24。比如：对于 $5,5,5,1$5,5,5,1，我们知道 $5*(5-1/5)=24$5∗(5−1/5)=24，因此可以得到$24$24，又比如：$1,1,4,2$1,1,4,2，我们怎么都不能得到$24$24。

**输入：**输入数据包括多行，每一行给出一组测试数据，包括$4$4个小于$10$10的正整数。最后一组测试数据包括$4$4个$0$0，表示输入的结束，这组数据不用处理。

**输出：**对于每一组测试数据，输出一行，如果可以得到$24$24，输出YES，否则，输出NO。

• 解题思路：$n$n个数算$24$24，必然要有两个数先算，这两个数算得的结果，和剩余的$n-2$n−2个数，构成了$n-1$n−1个数求$24$24的问题。可见问题的规模变小了，但是形式是一样的，可以采用递归进行求解。

  • 首先枚举先算的两个数，以及这两个数的运算方式，接着递归求解
  • 边界条件：当剩余$1$1个数时，判断是否等于$24$24。

• 示例代码

  #include <iostream>
  #include <cmath>
  using namespace std;
  double a[5];
  #define EPS 1e-6
  
  // 判断两个浮点数是否相等 
  bool isZero(double x) {
  	return fabs(x) <= EPS;
  }
  // 用数组 a 里面的数，计算24
  bool count24(double a[], int n) {
  	if(n == 1) {
  		if(isZero(a[0] - 24)) {
  			return true;
  		}
  		else {
  			return false;
  		}
  	}
  	double b[5];
  	for(int i=0; i<n-1; i++) {
  		for(int j=i+1; j<n; j++) {	// 枚举出所有两个数的组合 
  			int m = 0;
  			for(int k=0; k<n; k++) {
  				if(k != i && k!= j) {
  					b[m++] = a[k];	// 把其余的数放入 b 中 
  				}
  			}
  			b[m] = a[i] + a[j];
  			if(count24(b, m+1)) {
  				return true;
  			} 
  			b[m] = a[i] - a[j];
  			if(count24(b, m+1)) {
  				return true;
  			} 
  			b[m] = a[j] - a[i];
  			if(count24(b, m+1)) {
  				return true;
  			} 
  			b[m] = a[i] * a[j];
  			if(count24(b, m+1)) {
  				return true;
  			}
  			if(!isZero(a[j])) {
  				b[m] = a[i] / a[j];
  				if(coun t24(b, m+1)) {
  					return true;
  				}
  			}
  			if(!isZero(a[i])) {
  				b[m] = a[j] / a[i];
  				if(count24(b, m+1)) {
  					return true;
  				}
  			}
  		}
  	}
  	return false;
  } 
  
  int main() {
  	while(true) {
  		for(int i=0; i<4; i++) {
  			cin >> a[i];
  		}
  		if(isZero(a[0])) {
  			break;
  		}
  		if(count24(a,4)) {
  			cout<<"YES"<<endl;
  		} else {
  			cout<<"NO"<<endl;
  		}
  	}
  	return 0;
  }
  

总结与反思

• 递归问题的三种适用情况，最主要的应用是将问题分解为规模更小的子问题，且子问题与原问题的形式相同，可以用同样的方法进行求解。
• 递归边界条件的确定，边界条件的形式不止一种，只要能够避免无限递归下去即可。有递推公式的可以从递推公式确定边界条件，其他问题则需要从问题本身来判断边界条件
• 递归问题不适用与大规模问题，有可能出现递归深度过深，导致溢出。换句话说，递归会尝试所有的情况，进行重复及无效的工作，如果问题规模过大，应采用动态规划方法进行求解。

最后有需要工程文件的朋友可以在评论里说明（记得指明邮箱），小编看到后会第一时间发送到指定邮箱。文章如有不严谨之处，欢迎大家指正！！！