算法之递归

递归是计算机算法中一类较为经典的问题。本文首先总结递归的思想，然后上例题和代码

定义：从程序设计的角度来看，递归就是让程序自己调用自己的一种编程技巧
作用：递归通常可以将大型复杂问题转化为一个与原始问题相似的较小规模的问题来求解
应用场景：①子问题和原问题要执行的操作一样，且子问题规模更小；②不能无限制调用自身，需要有出口
思想：将待求解问题的解看作输入变量\(x\)的函数\(f(x)\)，通过寻找递归函数\(g\)，使得\(f(x)=g(f(x-1))\)，同时\(f(0)\)已知，根据递归函数和递归终止条件，就可递归求解了
推广：可以推广至多变量，也可以推广至\(x-2\)等，只要递归朝着出口方向前进即可

汉诺塔问题

白皮算法书4.3:

解题思路：将问题分解为以下三步
1. 将A下面的n个盘子，以C为中转，移动到B
2. 将A最下面的一个盘子移动到C
3. 将B下面的n-1个盘子，以A为中转，移动到C
上面的1和3步同原问题形式相同，规模减一，满足应用场景①，递归终止条件为，当n=1时，直接把A的盘子移动到C即可，因此满足递归的应用场景。

代码：

#include<iostream>
using namespace std;
// Hanoi函数作用：将src上的n个盘子，以mid为中转，移动到dest上
void Hanoi(int n, char src, char mid, char dest)
{
    if(n==1) // 递归终止条件
    {
        cout<<src<<"->"<<dest<<endl;
        return;
    }
    // 将src上的n-1个盘子，经dest，移动到mid上
    Hanoi(n-1, src, dest, mid);
    // 将src上的第n个盘子，直接放到dest上
    cout<<src<<"->"<<dest<<endl; // Hanoi(1, src, mid, dest);
    // 将mmid上的n-1个盘子，经src，移动到dest上
    Hanoi(n-1, mid, src, dest);
    return;
}
int main()
{
    int n=0;
    cout<<"汉诺塔问题求解，请输入一个正整数n，代表初始盘子的数量：";
    cin>>n; // 输入盘子的数量n
    Hanoi(n, 'A', 'B', 'C');
    // system("pause");
    return 0;
}

复杂度分析：

递归算法的复杂度通常用递推公式推导。假设问题规模为\(n\)，\(T(n)\)为所需的步骤，那么\(T(n)=1+2*T(n-1)=2^n-1+2^{n-1}T(1)=O(2^n)\)

小游戏

白皮算法书4.3:

解题思路：迷宫求解问题，自相似性表现在每走一步的探测方式相同，因此可用递归求解。
- 通过穷举的方式找到起点到终点的路径，朝一个方向走下去，如果走不通，则换一个方向走；四个方向都走不通，则回退到上一步，再换个方向走；依次走下去，直到终点
- 记录上一步走的方向，如果和下一步相同，则路径数不变，如果不同，则加一
- 用一个二维数组记录每个节点是否被走过

代码：

#include<iostream>
#include<cstring> // memset(数组名，值，sizeof(数组名))
using namespace std;

#define MAX_SIZE 75
char board[MAX_SIZE+2][MAX_SIZE+2]; // 定义地图
bool mark[MAX_SIZE+2][MAX_SIZE+2]; // 记录是否走过
int minSeg=100000, boardNum=0, w=0, h=0;
int to[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; // 定义方向：东南西北
/*
输入：
5 4
XXXXX
X   X
XXX X
 XXX 
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0
*/

// 函数DFS：输入为当前位置，结束位置，最短线段数seg和上一步的前进方向dir
void DFS(int currentX, int currentY, int endX, int endY, int seg, int dir)
{
    if(seg>=minSeg) // 剪枝
        return;
    if(currentX == endX && currentY == endY) // 递归边界条件
    {
        if(seg<minSeg)
            minSeg = seg;
        return;
    }
    for(int i=0; i<4; ++i)
    {
        int x = currentX+to[i][1];
        int y = currentY+to[i][0];
        // 这里的if条件只需要判断是否可以走，而不用管不可以走的
        if((x>=0 && x<=w+1 && y>=0 && y<=h+1) 
           && ((board[y][x]==false && mark[y][x]==' ')||(board[y][x]=='X' && x==endX && y==endY)))
        {
            mark[y][x]=true;
            if(i==dir) // 方向与上一步相同
                DFS(x,y,endX,endY,seg,i);
            else // 方向与上一步不同
                DFS(x,y,endX,endY,seg+1, i);
            mark[y][x]=false; // 回溯
        }
    }
    return;
}

int main()
{
    while(cin>>w>>h)
    {
        if(w==0&&h==0)
            return 0;
        boardNum+=1;
        cout<<"Board #"<<boardNum<<":"<<endl;
        for(int i=0; i<MAX_SIZE+2; ++i)
            board[0][i]=board[i][0]=' ';
        for(int i=1; i<=h; ++i)
        {
            getchar(); // 读入上一行回车
            for(int j=1; j<=w; ++j)
            {
                board[i][j]=getchar();
            }
        }
        for(int i=1; i<=h+1; ++i)
            board[w+1][i]=' ';
        for(int j=1; j<=w+1; ++j)
            board[h+1][j]=' ';
        int startX, startY, endX, endY, count=0;
        while((cin >> startX >> startY >> endX >> endY) && startX>0)
        {
            count++;
            minSeg = 1000000;
            memset(mark, false, sizeof(mark));
            DFS(startX, startY, endX, endY, 0, -1);
            if(minSeg<1000000)
                cout<<"Pair "<<count<<":"<<minSeg<<" Segments."<<endl;
            else
                cout<<"Pair "<<count<<":impossible."<<endl;
        }
        cout<<endl;
    }
    return 0;
}

实现技巧：
1. 可以使用一个二维数组来表示四个搜索方向，以东南西北四个搜索方向为例，可以定义为：
  
  int to[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
2. 判断下一步是否符合要求时，if条件为下一步可以走的地方，该地方满足两个条件，首先是在界内，其次没走过且为空格，或是终点
3. 注意将mark的标记和回溯问题，一般回溯都紧跟在递归方程后
复杂度分析：暂不分析

棋盘分割

白皮算法书4.4:

解题思路：自相似性表现在对于未分割棋盘也是同样的问题，只是规模减小了，因此利用递归计算
- \(\sigma=\sqrt{\frac{\Sigma_{i=1}^{n}(x_i-\bar{x})^2}{n}}=\frac{\Sigma{x_i^2}}{n}-\bar{x}^2\)，因此只需要计算最小的\(\Sigma{x_i^2}\)即可，其中\(x_i\)为第i块矩形棋盘的和
- 设目标函数为\(Fun(n,x_1,y_1,x_2,y_2)\)为左上角为\((x_1,y_1)\)，右下角为\((x_2,y_2)\)的棋盘，分割\(n\)次后，该种分割所有棋盘内分数和的平方，求和最小
- 递归方程为min{四个方向切（其实只有两个方向）哪个方向的平方最小{min{固定方向，切在哪里后两侧平方和最小}}

代码：

#include<iostream>
#include<cstring> // memset
#include<cmath>
#include<iomanip> // cout<<setiosflags(ios::fixed)<<setprecision(3)<<result<<endl;

using namespace std;

int s[9][9];
int res[15][9][9][9][9];
int sum[9][9]; // 记录(1,1)(i,j)围成矩形的和

/*
输入：
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

输出：1.633
*/

int CalSum(int x1, int y1, int x2, int y2)
{
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}

int min(int a, int b)
{
    return a<b?a:b;
}

int Fun(int n, int x1, int y1, int x2, int y2)
{
    if(res[n][x1][y1][x2][y2]!=-1)
    {
        return res[n][x1][y1][x2][y2];
    }
    if(n==1)
    {
        res[n][x1][y1][x2][y2]=pow(CalSum(x1,y1,x2,y2),2); 
        return res[n][x1][y1][x2][y2];
    }
    int MIN = 0xffffff;
    // 沿x方向切
    for(int i=x1; i<x2; ++i)
    {
        int up = CalSum(x1,y1,i,y2);
        int down = CalSum(i+1,y1,x2,y2);
        int temp = min(Fun(n-1,x1,y1,i,y2)+down*down, Fun(n-1,i+1,y1,x2,y2)+up*up); // 用上半部分继续切还是下半部分继续切
        MIN = min(MIN, temp); 
    }
    // 沿y方向切
    for(int j=y1; j<y2; ++j)
    {
        int left = CalSum(x1,y1,x2,j);
        int right = CalSum(x1,j+1,x2,y2);
        int temp = min(Fun(n-1,x1,y1,x2,j)+right*right,Fun(n-1,x1,j+1,x2,y2)+left*left); // 用左边还是右边继续切
        MIN = min(MIN, temp);
    }
    res[n][x1][y1][x2][y2]=MIN;
    return res[n][x1][y1][x2][y2];
}

int main()
{
    int n=0;
    cin>>n;
    memset(res,-1,sizeof(res));
    memset(sum,0,sizeof(sum));
    for(int i=1; i<9; ++i)
    {
        for(int j=1, rowSum=0; j<9; ++j)
        {
            cin>>s[i][j];
            rowSum += s[i][j];
            sum[i][j] = sum[i-1][j] + rowSum; // 以积分形式计算子块和
//            cout<<sum[i][j]<<" ";
        }
//        cout<<endl;
    }
	double result = sqrt((n*Fun(n,1,1,8,8) - pow(sum[8][8],2))/(n*n));
	// double result = sqrt(Fun(n,1,1,8,8)/n - pow(sum[8][8],2)/pow(n,2)); 注意这里虽然数学上一样，但是程序计算时和上方公式有一定的误差
    cout<<setiosflags(ios::fixed)<<setprecision(3)<<result<<endl;
    system("pause");
    return 0;
}

实现技巧：
1. 如果每一个\(Fun(n,x_1,y_1,x_2,y_2)\)都要重新计算，那么计算量一定会超时的，因此设立数组res[n][x1][y1][x2][y2]用来存储中间已经计算过的，防止重复计算
2. 用sum[i][j]数组来存储\((1,1)\)和\((i,j)\)所构成矩形的分数之和，并在输入矩阵是用当前行积分的形式，计算sum[i][j]
3. 注意如果最终结果只差一点点时，考虑是否是因为计算机数值计算时导致的误差造成的
4. 如何记录下切割方案？
复杂度分析：
- 因为需要遍历不同的切割方式，因此需要尝试77665*5...次（乘法次数为n-1），每次切割的计算为O(1)

八皇后问题

白皮算法书4.5: http://bailian.openjudge.cn/practice/2754

解题思路：自相似性表现在，对于前i行已经码好的情况下，只用遵循限制条件，将第i+1层码好即可（带回溯）
- 考虑将92个解全部解出并存储，避免后续重复计算
- 从第一个皇后的位置开始一个个的测试当前码放是否可行，不行的话进行回溯

代码：

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

int res[92][8];
int row[8]; // 第i行存放在了第row[i]列 
int cnt = 0;

/*
输入：
2
1
92
输出：
15863724
84136275
*/

void queen(int n)
{
	if(n == 8)
	{
		for(int i=0; i<8; ++i)
		{
			res[cnt][i] = row[i];
		}
		cnt++;
	 	return;
	}
	for(int i=1; i<=8; ++i) // 将当前皇后逐一尝试放在不同的列，每列对应一组解 
	{
		int j = 0;
		for(j=0; j<n; ++j) // 判断当前放置位置(n,i)是否和上方码好的皇后冲突(因此回溯时不用将下方的row值改回来) 
		{
			// 如果（n行，i列） 这个点的同列中有queen，即遍历row[j]，如果row[j]==i，则break 
			// 或者（8-1行，i列） 这个位置的对角线上有queen也要break，即当前码放点和之前码放点横纵坐标分别求差的绝对值相等 
			if(row[j]==i || abs(n-j)==abs(i-row[j]))
			{
				break;
			}
		} 
	 	if(j == n) // 如果当前方置位置(n,i)和上方皇后都不冲突 
	 	{
	 		row[n] = i; // 记录当前位置 
	 		queen(n+1); // 递归寻找下一层 
 		}
	}
}

int main()
{
	int n = 0, num = 0;
	cin >> n;
	memset(row, -1, sizeof(row));
	memset(res, -1, sizeof(res));
	queen(0);
	while(n--)
	{
		cin >> num;
		for(int i=0; i<8; ++i)
		{
			cout<<res[num-1][i];
		}
		cout << endl;
	} 
	return 0;
}

实现技巧：
- 将92种方案一次性算出来，而不是每次输入一个序号，就要从新训练一次
- 这里需要回溯，但是不用修改数组内容
- 是否在同一个斜线上的判断用的是abs(x1-x2)==abs(y1-y2)
复杂度分析：每一行都要试8个位置，每次尝试是\(O(1)\)的，一共有8行，因此复杂度是\(O(8^8)\)。

文件结构图

白皮算法书4.6: http://bailian.openjudge.cn/practice/2775/

解题思路：文件的结构就是递归的结构，每个目录都是一个小的文件结构。
- 当出现新的目录时就是递归的开始
- 当出现']'时就是当前递归的截至

代码：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> // sort(vector.begin(), vector.end());

using namespace std;

int n = 0;
bool fileStructure(int level, string dir)
{
	vector<string> file; // 用于存储当前目录下的文件 
	
	// 输出当前文件目录(根目录需要特殊处理) 
	if(level != 0)
	{
		for(int i=0; i<level; ++i) cout << "|     ";
		cout << dir << endl;
	}
	
	bool rFlag = false; 
	// 持续输入该文件夹下文件或文件夹 
	while(true)
	{
		string s;
		cin >> s;
		if(s == "#") return true;
		if(!rFlag && level==0)
		{
			cout << "DATA SET " << n << ":" << endl;
			cout << dir << endl; 
			rFlag = true;
		}
		
		if(s == "*") break;
		if(s == "]") break;
		if(s[0] == 'f') file.push_back(s); // 如果是文件则存入vector中 
		if(s[0] == 'd') fileStructure(level+1, s);  // 如果是文件夹则递归 
	}
	
	// 排序当前目录下文件，并输出
	sort(file.begin(), file.end());
	for(int i=0; i<file.size(); ++i)
	{
		for(int j=0; j<level; ++j) cout << "|     ";
		cout << file[i] << endl;
	} 
	return false;
}

int main()
{
	bool flag = false;
	while(true)
	{
		n++;
		flag = fileStructure(0, "ROOT");
		if(flag) break;
		cout << endl;
	}
	return 0;
}

实现技巧：
- 每一层递归都新建一个vector用于存储file文件，防止错乱，在当前层结束调用前输出排序输出file
- 注意string类型的变量需要用""来定义或赋值
- 注意根节点输出是特殊情况，需要特殊处理，不能放到主函数中
复杂度分析：这种题目好像无法计算复杂度。

算24

白皮算法书4.7:

解题思路：可以随机找到2个数，利用加减乘除进行运算后变为一个数，此时n个数变为了n-1个数，按照此方法规模不断减一，当只有一个数时，判断其是否为24，如果是则输出。

代码：

#include<iostream>
#include<cmath>

using namespace std;
int ans = 0;
void Calculate24(float* a, int n) // 注意这里传入的参数应该是float类型
{
    float b[3]; // 对于每两个数的运算都应该从新存入新的数组进行运算
    if(n == 1)
    {
        if(abs(a[0]-24)<0.0001) ans = 1;
        return;
    }
    for(int i=0; i<n; ++i) // 对于a中的每一个数，寻找与之配对的另一个数
    {
        for (int j=i; j<n; ++j)
        {
            if(i == j) continue;
            int m = 0; 
            for(int k=0; k<n; ++k)
            {
                if(k==i||k==j) continue;
                b[m] = a[k];
                m++;
            }
            b[m] = a[i]+a[j];
            Calculate24(b, m+1);
            b[m] = a[i]-a[j];
            Calculate24(b, m+1);
            b[m] = a[i]*a[j];
            Calculate24(b, m+1);
            if(a[j] != 0)
            {
                b[m] = a[i]/a[j];
                Calculate24(b, m+1);
            }
        }
    }
}

int main()
{
    float a[4];
    while(cin >> a[0] >> a[1] >> a[2] >> a[3] && a[0]+a[1]+a[2]+a[3]!=0)
    {
        ans = 0;
        Calculate24(a, 4);
        if(ans) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

实现技巧：

判断是否等于24：因为涉及除法，因此会产生浮点数，此时应判断if(abs(a-24)<0.0001)来判断是否等于24
括号运算符：因为每个数字的组合都会出现，且两数之间的每个运算符都会出现，因此隐含的表述了括号的存在
全局变量ans：该变量用于判定是否可以计算出24，每组样例输入后需要清零。同时递归函数就不用返回值了。数组b[3]也非常巧妙，保证了递归的形式，如果做为全局变量的话肯定不行，数据会脏。

减少重复计算次数：将递归中第二层循环从for(int j=0; j<n; ++j)变为for(int j=i; j<n; ++j)，此时减少了重复计算的次数，但是有一定的错误，因为四则运算中加法和乘法可以交换位置，但是减法和除法不行，因此需要在内层循环中加入减法和除法的反向操作，改进后递归函数如下，时间从686ms减少到了263ms

void Calculate24(float* a, int n) // 注意这里传入的参数应该是float类型
{
    float b[3]; // 对于每两个数的运算都应该从新存入新的数组进行运算
    if(n == 1)
    {
        if(abs(a[0]-24)<0.0001) ans = 1;
        return;
    }
    for(int i=0; i<n; ++i) // 对于a中的每一个数，寻找与之配对的另一个数
    {
        for (int j=i; j<n; ++j)
        {
            if(i == j) continue;
            int m = 0; 
            for(int k=0; k<n; ++k)
            {
                if(k==i||k==j) continue;
                b[m] = a[k];
                m++;
            }
            b[m] = a[i]+a[j];
            Calculate24(b, m+1);
            b[m] = a[i]-a[j];
            Calculate24(b, m+1); // 加入反向减法
            b[m] = a[j]-a[i];
            Calculate24(b, m+1);
            b[m] = a[i]*a[j];
            Calculate24(b, m+1);
            if(a[j] != 0)
            {
                b[m] = a[i]/a[j];
                Calculate24(b, m+1);
            }
            if(a[i] != 0) // 加入反向除法
            {
                b[m] = a[j]/a[i];
                Calculate24(b, m+1);
            }
        }
    }
}

复杂度分析：\(O(n!*(n-1)!)\)，对于4个数字的情况，第一次递归要选择两个数，也就是\(C_4^2\)次，第二层递归要计算\(C_3^2\)次，以此类推

汉诺塔用栈代替递归

白皮算法书4.8:

解题思路：
- 手动维持一个栈，对于当前问题，同样拆解为3步，压入栈中，然后从栈顶开始取元素，以此类推来完成
代码：
1
实现技巧：
- 用结构体定义当前状态，用结构体类型的数组完成栈中每个元组的存储。栈的大小不超过n的3倍