递归

递归的概念

• 一个函数调用自身就是递归
• 递归和普通函数调用都是通过栈实现的；栈中存的是：形参、局部变量、返回地址，栈顶放返回值，函数调用结束时从站顶开始退栈；

递归的作用

• 替代多重循环
• 解决用递归形式定义的问题
• 将问题分解为规模更小的字问题进行求解

汉诺塔问题

#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;
}