递归的概念
- 一个函数调用自身就是递归
- 递归和普通函数调用都是通过栈实现的；栈中存的是：形参、局部变量、返回地址，栈顶放返回值，函数调用结束时从站顶开始退栈；
递归的作用
- 替代多重循环
- 解决用递归形式定义的问题
- 将问题分解为规模更小的字问题进行求解
汉诺塔问题
#include <iostream>
using namespace std;
// 每次实际移动的时候，只移动了一个盘子
// 将src座上的n个盘子，以midw座为中转，移动到dest座
// src座上最上方盘子编号是src_n
void Hanoi(int n, char src, char mid, char dest, int src_n)
{
//cout << "In Hanoi" << endl;
// 只需移动一个盘子：直接将盘子从src移动到dest即可
if(n == 1) {
cout << src_n << ":" << src << "->" << dest << endl;
return;
}
// 先将上面n-1个盘子从src移动到mid上
Hanoi(n - 1, src, dest,mid,src_n);
// 再将最下面的即第n个盘子从src移动到dest
cout << src_n + n - 1 << "---" << src << "->" << dest << endl;
// 将n-1个盘子从mid移动到dest
Hanoi(n - 1, mid, src, dest, src_n);
return;
}
int main()
{
char a, b, c;
int n;
cin >> n >> a >> b >> c;
Hanoi(n, a, b, c, 1);
return 0;
}
3 A B C
1:A->C
2---A->B
1:C->B
3---A->C
1:B->A
2---B->C
1:A->C
n皇后问题
/*
* 将n个皇后放在一张nxn的的棋盘上，使得每位皇后都无法吃掉别的皇后，
* （即任意两个皇后都不在同一条横线，竖线和斜线上）；求一共有多少种摆法；
*/
#include <iostream>
#include <cmath>
using namespace std;
#define MAX_NUM 100
int N; // n个皇后
int queenPos[MAX_NUM];
void NQueen(int k);
int main()
{
cin >> N;
NQueen(0); // 从第0行开始摆放皇后
return 0;
}
// 在第0～第k-1行皇后已经摆好的情况下，摆第k行及其后的皇后
void NQueen(int k)
{
int i;
// N个皇后已经摆好了
if(k == N) {
for(i = 0; i < N; i++) {
cout << queenPos[i] + 1 << " ";
}
cout << endl;
return;
}
// 逐个尝试第k个皇后的位置
for(i = 0; i < N; i++) {
int j;
// 和已经摆好的k个皇后的位置比较，看是否冲突
for(j = 0; j < k; j++) {
if(queenPos[j] == i || // 在同一列
abs(queenPos[j] - i) == abs(k-j)) { // 在对角线上，即二者行的差和列的差相等
break;
}
}
if(j == k) {
queenPos[k] = i;
NQueen(k+1);
}
}
}
// output
4
2 4 1 3
3 1 4 2
逆波兰表达式
- 一个数是逆波兰表达式，值为该数
- “运算符 逆波兰表达式 逆波兰表达式”是逆波兰表达式，值为两个逆波兰表达式的值运算的结果
#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);
break;
}
}
int main()
{
printf("%lf", exp());
return 0;
}
