递归的基本概念 

 

• 一个函数调用其自身，就是递归 

• 递归需要终止条件，否则就会无穷递归导致程序无法终止甚至崩溃

• 递归和普通函数 调用一样是通过 栈实现的。每调用一次，栈就像上长一层

求阶乘

#include <iostream>
#include <cstdio>
using namespace std;
int Fact(int n){
	//函数，返回n的阶乘 
	if(n<2)
		return 1;//终止条件 
	return n*Fact(n-1);
}
int main(){
	int n;
	cin >>n;
	cout << Fact(n); 
}

汉诺塔问题

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

N皇后问题

• 在国际象棋的棋盘上，按照国际象棋的规则，摆放N个皇后，使之“和平共处”。如图所示，在3-D上有一个皇后，则绿色区域中都不能再放置皇后了。
• 最暴力的方法就是使用for循环，但是很明显，这种方法效率太低。
• 对于放置了皇后的位置，仔细观察棋盘可以发现每一列（行）只能有一个皇后，每一个主（次）对角线上也只能有一个皇后

#include <iostream>
#include <cstdio>
#include <cmath> 
using namespace std;
int N;//N个皇后 
int queenPos[100];//存放第i行的皇后应该放在哪一列 
void NQueen(int k);
int main(){
	cin >>N;
	NQueen(0);//从第0行开始摆皇后
	return 0; 
} 
void NQueen(int k){
//在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后 
	int i;
	if(k==N){//N个皇后已经摆好，输出 
		for(i=0;i<N;i++)
			cout <<queenPos[i]+1<<" ";
		cout <<endl;
		return; 
		
	}
	for(i=0;i<N;i++){//逐渐尝试第k个皇后的位置 
		int j;
		for(j=0;j<k;j++){//和前面的K个皇后位置进行比较
			//行的差的绝对值和列的差的绝对值相同，说明在对角线上，能够吃到
			if(queenPos[j]==i||abs(queenPos[j]-i)==abs(k-j)){
					break;//冲突，测试下一个位置 
				}
		} 
		if(j==k){//当前选的位置与前k个不冲突 
			queenPos[k]=i;
			NQueen(k+1); 
		}
	} 
}

逆波兰表达式

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

爬楼梯

• n级台阶的走法 =先走一级后，n-1级台阶的走法 + 先走两级后，n-2级台阶的走法
• f(n) = f(n-1)+f(n-2)

#include <iostream>
#include <cstdio>
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 <<stairs(N)<<endl;
	}
}

放苹果

#include <iostream>
#include <cstdio>
using namespace std;
int f(int m,int n){//m，苹果数量，n，盘子数量
	if(m<n)return f(m,m);
	if(m==0)return 1;// 没有苹果，则不放，是一种方法 
	if(n<=0)return 0;//有苹果，没有盘子，返回0 
	//苹果数量>盘子数量 
	return f(m,n-1)+f(m-n,n); 
}
int main(){
	int m,n;
	cin >> m >> n;
	cout << f(m,n)<<endl;
	return 0;
}

算24

• n个数算24，必有两个数要先算。这两个数算的结果，和剩余n-2个数，就 构成了n-1个数求24的问题
• 枚举先算的两个数，以及这两个数的运算方式
• 边界条件：一个数算24
• 注意：浮点数比较是否相等，不能用 == 

#include <iostream>
#include <cstdio>
#include <cmath>
#define EPS 1e-6
using namespace std;
double a[5];//存放4个数 
bool isZero(double x){
	return fabs(x)<=EPS;
}
bool cout24(double a[],int n){//用数组a里的n个元素去计算24
	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++){//选出两个数 a[i],a[j]用来做运算，然后把算出来的结果和剩下的两个数存在b数组 
			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];//依次将取出的两个数运算的结果放入b 
			if(cout24(b,m+1))return true;
			b[m]=a[i]-a[j];
			if(cout24(b,m+1))return true;
			b[m]=a[j]-a[i];
			if(cout24(b,m+1))return true;
			b[m]=a[i]*a[j];
			if(cout24(b,m+1))return true;
			if(!isZero(a[j])){
				b[m]=a[i]/a[j];
				if(cout24(b,m+1))return true;
			}
			if(!isZero(a[i])){
				b[m]=a[j]/a[i];
				if(cout24(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; //输入0退出 
		if(cout24(a,4)){
			cout << "YES" << endl;
		}else{
			cout <<"NO"<<endl;
		}
	}
	return 0;
}