《算法笔记》总结No.5——递归

一.分而治之

将原问题划分为若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解，步骤抽象如下：

1. 分解：将原问题分解为若干子问题
2. 解决：递归求解所有子问题，如果子问题的规模小到可以直接解决，就直接解决它
3. 合并：将子问题的解合并为原问题的解

子问题之间应该是相互独立且没有交叉的，从严格的定义上将，子问题个数为1的情况称为减治，而大于1的情况称为分治。

分治法作为一种思想，即可使用递归的手段去实现，也可以通过非递归的手段去实现。

二.递归

递归的一个很符合精髓且搞笑的定义：要理解递归，你要先理解递归，直到你能理解递归为止。

递归的核心在于——反复调用自身函数，但是每次能把问题范围缩小，直到范围缩小到可以直接得到边界数据的结果，然后再在返回的路上求出对应的解。

两个重要概念：

• 递归边界：分解问题的尽头
• 递归式（或者称之为递归调用、递归函数）：分解子问题的手段

        如果使用递归而式而不进行阻止，那么最后将会无法停止这个黑洞似的无穷尽的算法。递归的代码结构中移动存在上述两个概念，他们支撑起了整个递归最关键的逻辑。

三.递归计算阶乘

直接先上代码：

#include <iostream>
using namespace std;

int F(int n){
	if(n==0) 
		return 1;
	else
		return F(n-1)*n;
}
 
int main() {
	int n=0;
	cin>>n;
	cout<<F(n);
	return 0; 
}

仔细观察，不难发现：

• 递归边界：n==0
• 递归式：F(n-1)*n

来仔细的分析一下，对于F(5)来说——相当于是F(4)*5,以此类推，直接将F(5)分解到了F(0)，此时F(0)=1，即子问题的答案，再将所有子问题的答案合并，即可完成本次求解~

假设输入的是3，则推倒过程依次为：

• F(3)
• F(2)*3
• F(1)*2*3
• F(0)*1*2*3
• 得到最后的F(0)的值以后，再返回去依次计算F(1)、F(2)、F(3)

四.递归计算裴波那契数列

#include <iostream>
using namespace std;

int F(int n){
	if(n==0||n==1) 
		return 1;
	else
		return F(n-1)+F(n-2);
}
 
int main() {
	int n=0;
	cin>>n;
	cout<<F(n);
	return 0; 
}

仔细观察，也没什么难度：

• 递归边界：0和1的返回值均为1
• 递归式：根据定义，第三项开始即为前两项的和

        对于这类递归问题，只要找到了递归边界和递归式，写起来代码就没什么难度。递归边界用来返回最简单底层的结果，递归式用来减小规模并进一步向下一层递归。递归图可以将递归放在一个平面上思考，有利于更快分析题目~

五.全排列

        某种意义上来说，学会递归的思维正是从一个只会暴力的小白蜕变的过程，比如当我们要求输入1~n之间数的全排列，如果硬碰硬直接霸王硬上弓，这个复杂度简直不能想象——毕竟光数量都达到n的阶乘个，何况找起来也是很费事的。

        从递归的角度去考虑，如果把问题描述成“1~n这n个整数的全排列”，那么就可以拆分为若干个子问题：“输出以1开头的全排列”、“输出以2开头的全排列”……以此类推。不妨设置一个数组P，用来存放当前的排列；再设置一个散列数组hashTable，其中hashTable[x]当x已在P中时赋值为true。

        现在按照顺序往P中的第1位到第N位填入数字。不妨假设当前已经填好了1~index-1位，正准备去填写index位。我们需要枚举1~n，如果当前枚举的数字x还没哟再1~index-1中，即填入到index位，同时设置hashTable[x]为true，然后去处理index+1位；如果递归完成时，以便让P[index]填写下一个数字。

#include <cstdio>
#include <iostream> 
using namespace std;
const int maxn=11;

int n,P[11],hashTable[maxn]={false};
//p为当前排列
//hashTable用来记录x是否已经在P中！ 

void generateP(int index)  //当前处理的正是第index位 
{
	if(index==n+1) //1~n已经处理完了，所以相当于n+1为递归边界~ 
	{
		for(int i=1;i<=n;i++)
			cout<<P[i];  //输出当前排列 
		cout<<endl;
		return;
	}
	for(int x=1;x<=n;x++)   //枚举1~n，试图将x填入到P[index]位上！ 
	{
		if(hashTable[x]==false)   //false即表示不存在~ 
		{
			P[index]=x;   //填入到index位 
			hashTable[x]=true;  
			generateP(index+1);  //递归处理下一位：即index+1 
			hashTable[x]=false;
		}
	}
}
 
int main() {
	n=3;
	generateP(1);
	return 0; 
}

• 递归边界：index==n+1
• 递归式：generateP(index+1);

六.N皇后问题

        N 皇后问题指的是如何将 N 个皇后放置在 N × N 的棋盘上，并且使皇后彼此之间不能相互攻击。即给你一个整数 N ，返回所有不同的 N 皇后问题的解决方案数量~

        这玩意，不知道大家有没有想起来行列式的定义：将行列式视为从矩阵的不同行和不同列中选取元素并相乘的代数和。每一项的符号由列标的逆序数决定，即如果列标的逆序数为奇数，则该项为负；若为偶数，则该项为正——其实就是全排列~不过不同的是，行列式可以在对角线上选择元素，而对于可以斜线行走的皇后，这一点显然也是不行。因此可以基于全排列的代码，然后对每一个全排列的结果进行单独判断是否存在对角线元素，即可完成~ 

 如下：判断是否在同一对角线，只需要看行距之差和列距之差的绝对值是否相同，即可：

int count=0;
void generateP(int index)  //当前处理的正是第index位 
{
	if(index==n+1) //1~n已经处理完了，所以相当于n+1为递归边界~ 
	{
		bool flag=true;  //flag为true时表示当前为一个合法方案~ 
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
				if(abs(i-j)==abs(P[i]-P[j])) 
					flag=false;   //不合法 	
		}
		if(flag)
			count++;
		return;
	}
	for(int x=1;x<=n;x++)   //枚举1~n，试图将x填入到P[index]位上！ 
	{
		if(hashTable[x]==false)   //false即表示不存在~ 
		{
			P[index]=x;   //填入到index位 
			hashTable[x]=true;  
			generateP(index+1);  //递归处理下一位：即index+1 
			hashTable[x]=false;
		}
	}
}

对于递归，只要想清楚边界、递归式、问题需要的答案，就没什么难度~